Permutation

[Kelly Booth]

In article <6315 at watdcsu.waterloo.edu> campbell at watdcsu.waterloo.edu (Colin Campbell [DCS]) writes:
>In article <16385 at watdragon.waterloo.edu> leung at gwchem.waterloo.edu (K.W. Leung) writes:
>>Does anyone out there have a C program which can generate all distinct
>>permutations of n symbol? I need this to generate some graphs. 

If you want all permutations on n symbols, with each permutation
produced as the result of a single interchange of two symbols from the
previously produced permutation, use Tritter's algorithm.  It's in
Knuth (I think).  This has the advantage of being O(1) per permutation
after O(n) setup time.

Otherwise, the obvious recursive algorithm ("for each value of the nth
symbol, generate all permutations of the n-1 remaining symbols") will
give you the answer, but the computation is O(n) between some
consecutive permutations because the recursion unwinds all the way.
Tritter's algorithm uses a clever bookeeping scheme to do away with the
recursion.