We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #24: Lexicographic permutations
  4. Discussions

Project Euler #24: Lexicographic permutations

Sort by

recency

|

44 Discussions

|

  • thummaganti_rav1
     + 0 comments

    //C# using System; using System.Collections.Generic;

    class Program { const int mod = 1000000007;

    static long Fact(long n)
{
    if (n <= 1)
        return 1;

    return Fact(n - 1) * n;
}

static void Solve()
{
    long n = long.Parse(Console.ReadLine());
    n--;
    List<char> alpha = new List<char> { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm' };
    string ans = "";

    for (int i = 12; i >= 0; --i)
    {
        long factorial = Fact(i);
        long x = n / factorial;

        ans += alpha[(int)x];
        n -= factorial * x;

        alpha.RemoveAt((int)x);
    }

    Console.WriteLine(ans);
}

static void Main()
{
    int t = int.Parse(Console.ReadLine());

    while (t-- > 0)
    {
        Solve();
    }
}

    }

  • alhassanchoubas1
     + 0 comments

    Python Solution

    We have 13! possible combinations of the string 'abcdefghijklm'. In it, there are 12! * 13 combinations, each of which has a, b, c, ... m in the beginning. In each of those combinations, there are 11! * 12 combinations, housing the leftover letters.

    def factorial(n):
    if n == 1:
        return 1
    
    return n * factorial(n - 1)
    
permutations = [factorial(i) for i in range(12, 0, -1)]

for _ in range(int(input())):
    N = int(input()) - 1
    ret = ''
    letters = list("abcdefghijklm")
    
    for i in permutations:
        q, N = divmod(N, i)
        ret += letters.pop(q)
        
    ret += letters[0]
        
    print(ret)

  • Venkateshgurram5
     + 0 comments
    from math import factorial

def nth_permutation(word,n):
    factoradic=[]
    word=list(word)
    for i in range(len(word) - 1, -1, -1):
        f=factorial(i)
        factoradic.append(n//f)
        n=n%f  
    return ''.join([word.pop(j) for j in factoradic])
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    word='abcdefghijklm'
    print(nth_permutation(word,n-1))

  • akashghosh559
     + 0 comments

    in python3

    def factorial(n): result = 1 for i in range(1, n+1): result *= i return result

    def nth_lexicographic_permutation(n, word): n -= 1 # Adjusting for 0-based indexing factorials = [factorial(i) for i in range(len(word))] result = "" available = list(word) for i in range(len(word), 0, -1): index = n // factorials[i-1] n = n % factorials[i-1] result += available.pop(index) return result

    word = "abcdefghijklm" for _ in range(int(input().strip()) n = int(input().strip()) result = nth_lexicographic_permutation(n, word) print(result)

        index = n // factorials[i-1]
    n = n % factorials[i-1]
    result += available.pop(index)
return result

  • ketan_patel25
     + 0 comments

    JAva code

    import java.io.*;
import java.util.*;

public class Solution {

    // public static void main(String[] args) {
    //     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    // }
     static long[] fact = new long[14];

    public static void main(String[] args) {
        factorialFill();

        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        for (int a0 = 0; a0 < t; a0++) {
            long n = scanner.nextLong();
            int[] arrc = new int[13];
            factorialNum(n - 1, arrc);
            printPermutation(arrc);
            System.out.println();
        }
        scanner.close();
    }

    static void factorialFill() {
        fact[0] = 1;
        for (int i = 1; i < 14; i++) {
            fact[i] = i * fact[i - 1];
        }
    }

    static void factorialNum(long n, int[] arrc) {
        long tmp = n;
        int index = 0;
        for (int i = 13; i >= 0; i--) {
            if (fact[i] <= tmp) {
                index = i;
                break;
            }
        }

        long q, r;
        while (index >= 0) {
            q = tmp / fact[index];
            r = tmp % fact[index];
            arrc[index] = (int) q;
            tmp = r;
            index--;
        }
    }

    static void updateList(char[] str, int index) {
        for (int i = index + 1; i <= 12; i++) {
            str[i - 1] = str[i];
        }
    }

    static void printPermutation(int[] arrc) {
        char[] str = "abcdefghijklm".toCharArray();
        for (int i = 12; i >= 0; i--) {
            System.out.print(str[arrc[i]]);
            updateList(str, arrc[i]);
        }
    }
}