Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Rajib_119's blog

Find permutation

By Rajib_119, 12 years ago, In English

How can I find the 1000th permutation of 50!. Using Backtrack i can easily find the 100th permutation of 5! or 5th permutation of 3! which is 3 1 2.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Assume that you have to find the K-th permutation with N elements. With fixed first element you can rearrange the other elements in (N-1)! ways. Now you can easily find the first element in the K-th permutation. Then do the same with the second element, and then with the third and so on.

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://swiyu.wordpress.com/2012/10/11/find-all-permutation-find-kth-permutation/

→ Reply
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

http://ideone.com/yP5KuJ

for understanding refer to Factorial number system Wiki page Complexity (n lg(n)^2 )

→ Reply