## Thursday, March 24, 2005

### 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):mainInterpreted + native   Method                   0.2%     3  +     0    permu.permute0.1%     1  +     0    permu.rpermute0.1%     1  +     0    permu.main0.3%     5  +     0    Total interpreted Compiled + native   Method                   50.5%   792  +     0    permu.permute49.2%   772  +     0    permu.rpermute99.7%  1564  +     0    Total compiledFlat profile of 0.01 secs (1 total ticks): DestroyJavaVMThread-local ticks:100.0%     1             Blocked (of total)Global summary of 17.74 seconds:100.0%  1577             Received ticksjava -Xprof permu 12Flat profile of 215.68 secs (18868 total ticks): mainInterpreted + native   Method                   0.0%     1  +     0    permu.rpermute0.0%     1  +     0    Total interpreted Compiled + native   Method                   50.6%  9544  +     0    permu.permute49.4%  9323  +     0    permu.rpermute100.0% 18867  +     0    Total compiled

C++ execution time

/usr/bin/time ./permu 100.23user 0.00system 0:00.31elapsed/usr/bin/time ./permu 1230.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