Massive Algorithms: Yu's Coding Garden : leetcode Question 68: Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

A better way is to fully use the properties of permutation: the total number of permutation with length n is n!.

Major steps are swap and fix:

Here in order to grow the tree, every time start the first unfixed element in each node, generate child nodes by swapping the first element with every other element.The leave nodes are those do not have element to swap.

ABC

/ | \

ABC BAC CBA

/ \ / \ / \

ABC ACB BAC BCA CBA CAB

Every leave node is a permutation. Take a look at the second level, each subtree (second level nodes as the root), there are (n-1)! permutations in it. Totally there are n nodes in 2nd level, thus the total number of permutations are n*(n-1)!=n!.

Say we have the required permutation is the kth one, first we can locate which subtree it belongs to in the 2nd level, by computing s = k / ((n-1)!). Then we get the sth subtree, and set k=k%((n-1)!) , now search the sub tree until we get the leave node.

From http://blog.csdn.net/lqcsp/article/details/23322951

接下来我们一个一个数的选取，如何确定第一个数应该是哪一个呢？选取第一个数后剩下全排列的个数为(n-1)! 所以选取的第一个数应该为第

K1 = k；

a1 = K1/(n-1)!位数字

同理当选完a1后只剩下n-1个数字，在确定第二个数应该选择哪个.

a2 = K2 / (n-2)!

K2 = K1 % (n-1)!

........

a(n-1) = K(n-1) / 1！

K(n-1) = k(n-2) % 2!

an = K(n-1)

Java Implementation from http://www.programcreek.com/2013/02/leetcode-permutation-sequence-java/

 public String getPermutation(int n, int k) {
 
  // initialize all numbers
  ArrayList<Integer> numberList = new ArrayList<Integer>();
  for (int i = 1; i <= n; i++) {
   numberList.add(i);
  }
 
  // change k to be index
  k--;
 
  // set factorial of n
  int mod = 1;
  for (int i = 1; i <= n; i++) {
   mod = mod * i;
  }
 
  String result = "";
 
  // find sequence
  for (int i = 0; i < n; i++) {
   mod = mod / (n - i);
   // find the right number(curIndex) of
   int curIndex = k / mod;
   // update k
   k = k % mod;
 
   // get number according to curIndex
   result += numberList.get(curIndex);
   // remove from list
   numberList.remove(curIndex);
  }
 
  return result.toString();
 }

Also refer to http://www.programcreek.com/2013/02/leetcode-permutation-sequence-java/
http://blog.csdn.net/lqcsp/article/details/23322951
Read full article from Yu's Coding Garden : leetcode Question 68: Permutation Sequence

Yu's Coding Garden : leetcode Question 68: Permutation Sequence

Labels

Popular Posts