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.

# 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

:)

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

hrushikeshvanga1 + 1 comment **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)

K_Abhishek + 1 comment can u jus explain this

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

Load more conversations

Sort 30 Discussions, By:

Please Login in order to post a comment