Iterative permutations

I spent quite a bit of time investigating permutations. The easiest known method for generating permutations is recursion. Iterative permutations are hard but not impossible. A quick comparison showed the following results. The C/C++ code without profiling was about 4-7 times faster than the java implementation.

The profiling had an impact on the C/C++ code. Java did better with profiling.

The recursive and the non-recursive versions did almost equally well. Here are some results for lengths 10 and 12.

Java Profile

Flat profile of 17.65 secs (1569 total ticks):
main

Interpreted + native   Method                   
0.2%     3  +     0    permu.permute
0.1%     1  +     0    permu.rpermute
0.1%     1  +     0    permu.main
0.3%     5  +     0    Total interpreted

 Compiled + native   Method                   

50.5%   792  +     0    permu.permute
49.2%   772  +     0    permu.rpermute
99.7%  1564  +     0    Total compiled

Flat profile of 0.01 secs (1 total ticks): 
DestroyJavaVM

Thread-local ticks:

100.0%     1             Blocked (of total)

Global summary of 17.74 seconds:

100.0%  1577             Received ticks

java -Xprof permu 12

Flat profile of 215.68 secs (18868 total ticks): 
main

Interpreted + native   Method                   
0.0%     1  +     0    permu.rpermute
0.0%     1  +     0    Total interpreted

 Compiled + native   Method                   

50.6%  9544  +     0    permu.permute
49.4%  9323  +     0    permu.rpermute
100.0% 18867  +     0    Total compiled

C++ execution time

/usr/bin/time ./permu 10
0.23user 0.00system 0:00.31elapsed

/usr/bin/time ./permu 12
30.44user 0.20system 1:28.34elapsed

rpermute is the recursive version of the permutation generator and permute is the lexicographic permutation generator. As can be seen, the execution times are almost the same. As far as the stack size is concerned, the iterative version uses a stack size of "s" and the recursive version goes upto a worst case of "ns".

The development of rpermute is much easier compared to the iterative version