2012/12/21

Next Permutation


  1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation. 
  2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index. 
  3. Swap s[i] with s[j]. 
  4. Reverse all the order of all of the elements after index i



private void getNext()
{
  int i = N - 1;

  while (Value[i-1] >= Value[i]) i = i-1;


  int j = N;


  while (Value[j-1] <= Value[i-1]) j = j-1;


  swap(i-1, j-1);    // swap values at positions (i-1) and (j-1)


  i++; j = N;


  while (i < j)
  {
    swap(i-1, j-1);
    i++;
    j--;
  }
}

參考資料:
http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string
http://www.freewebs.com/permute/lexico.html

No comments:

Post a Comment