Thursday, October 6, 2011

Write a function for computing next permutation of a string

This is a little pearl piece of code

void printVector(int * value, int N)
{
 for (int i = 0; i < N; i++)
  std::cout << value[i] << " " ;

 std::cout << std::endl;
}

void visit(int * value, int N, int K)
{
 static int level = -1;

 level++; value[K] = level;    // the level is current i 

 if (level == N)               // a complete permutation
  printVector(value, N);
 else
  for (int i = 0; i < N; i++)  // 0... N-1
   if (value[i] == 0)             // not used before
    visit(value, N, i);

 level--; value[K] = 0;   // nothing else to explore for the level, ready for next round of usage
}

The above is cooler than the classical recursive solution
A permutation of 1,2,3,4 would be:
1 + permutation_of(2,3,4)
2 + permutation_of(1,3,4)
3 + permutation_of(2,1,4)
4 + permutation_of(2,3,1)

2 comments:

  1. Interesting reading http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

    ReplyDelete
  2. and also
    http://nicolas-lara.blogspot.com/2009/01/permutations.html

    ReplyDelete