Блог пользователя Rajib_119

Find permutation

Автор Rajib_119, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

http://ideone.com/yP5KuJ

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

→ Ответить