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)

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

ReplyDeleteand also

ReplyDeletehttp://nicolas-lara.blogspot.com/2009/01/permutations.html