# Project Euler #24: Lexicographic permutations

# Project Euler #24: Lexicographic permutations

VadimKey + 7 comments Factorial number systems allows to solve this problem for O(1) time: https://en.wikipedia.org/wiki/Factorial_number_system

:)

vicennial + 0 comments Hi, Could you please explain how to use this method?

I couldnt find any resources online explaining how to do so.

Thanks!kilicars + 0 comments [deleted]sakets594 + 0 comments very helpful

Harrison_Shen + 0 comments That is called reversed Cantor expansion method.

kedavamaru + 0 comments I didn't know about that, so i followed my intuition and ended up creating a method to map from N to the n'th lexicographic permutation, I'm happy to see that both methods are the same! It was awesome to conclude it on my own

1634810114_coe3b + 0 comments One of the best question of project eluer .

khoangcachxalam1 + 0 comments thank for your suggestions very much :) ...

aa1992HackerRank Admin + 2 comments very interesting problem...enjoyed solving it

shashank21jHackerRank AdminChallenge Author + 0 comments Thanks :)

eslamsamymeg + 0 comments Me too :D

driftwood + 0 comments ### C++ USERS

**Tips:**-You may be tempted to create a

`vector<>`

of all possible permutations using`next_permutation`

to easily access the ith element; there are far to many permutations needed to use this method given the time limits-There are N! permutations of a char within a string of size N, and there are further {(N-1)! to (N=1)!}permutations:

- Recursive
`function`

- Start call with
`k`

th permutation and original`string`

- Find
`factorial`

of string.size()-1 - Find
`X`

= k/factorial and`Y`

= k%factorial - Hold the
`X`

th character,`j`

, of`string`

and remove it from`string`

- Return
`j`

and call`function`

(`Y,string`

) - Print
`function`

's return

- Recursive

vicennial + 0 comments Just solved it using factorial number system! Learnt it in the process and it is an awesome concept.

d_rhidians + 1 comment python 3 solution

from math import factorial as fact def swapPos(x, y): for i in range(y , x , -1): s[i],s[i-1] = s[i-1], s[i] def findFact(x, k, pos = 0): if (k == 0): return swapPos(pos, (x - 1) // fact(k) + pos) findFact( (x - 1) % fact(k) + 1, k - 1, pos + 1) for _ in range(int(input())): n = int(input()) s = list('abcdefghijklm') k = len(s) - 1 findFact(n, k) print(''.join(s))

riyaparuthi21 + 0 comments Can you pls explain the logic behind it with comments in the program.

vardhan_reddy_ + 0 comments @aiswaryamathur/find-the-n-th-permutation-of-an-ordered-string-using-factorial-number-system-9c81e34ab0c8">https://medium.com/@aiswaryamathur/find-the-n-th-permutation-of-an-ordered-string-using-factorial-number-system-9c81e34ab0c8

This gives you a clear explaination.

ynerush + 1 comment Easy solved with Java by recursion using factorial that takes around 0.33s running time per test case.

cantonios + 2 comments There's a faster way. There's a simple formula that can determine the index of the next letter. Mine simply says 0s for all test cases.

westsiderz + 0 comments Thanks a lot for the hint. It was the most useful one. Really saved me lots of time.

anand_10 + 0 comments What ???

vikram777 + 0 comments why my 7,8 and 9 test case are wrong

#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ long long int n; cin>>n;n--; string fact = ""; int i=1; while(n){ fact = to_string(n%i) + fact; n/=i; i++; } fact = string(13-fact.length(),'0') + fact; //cout<<fact<<"\n"; string res = "abcdefghijklm",result; for(int i=0;i<fact.length();i++){ int index = (fact[i]-'0'); result+=res[index]; res.erase(index, 1); } cout<<result<<"\n"; } return 0; }

horowitz_jeffrey + 0 comments #Simple Ruby solution word = 'abcdefghijklm' def factorial(n) return n <= 1 ? 1 : n*factorial(n-1) end t = gets.strip.to_i for a0 in (0..t-1) n = gets.strip.to_i letters = word.split(//) permutation = [] letter_count = letters.size k = factorial(letter_count) letter_count.downto(1) { |num_letters| k /= num_letters offset = (n-1)/k permutation << letters[offset] letters.delete_at(offset) n -= (k*offset) } puts permutation.join end

hrushikeshvanga1 + 0 comments **Got all testcases in 0.04. Simply use factorial no system**string = "abcdefghijklm" def find_fac(no): i = 1 while no!=0: fac[13 - i] = no % i no = no // i i += 1 return fac def find_string(fac): arr = list(string) result = "" for i in range(len(fac)): result += arr.pop(fac[i]) return result t = int(input()) for i in range(t): fac = [0] * 13 no = int(input()) no = no - 1 fac = find_fac(no) # print(fac) result = find_string(fac) print(result)

Sort 26 Discussions, By:

Please Login in order to post a comment