🚀 go-pugleaf

In article <16385@watdragon.waterloo.edu> leung@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. 
>
>Thanks in advance.
>					Kamiwuni

You might be interested to know of Maple's permute function, e.g.:
     permute([a,b,c]);
            [[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]]
or:
     permute(3);
            [[1,2,3], [1,3,2], ...]
or:
     permute(3,2);
            [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]

In article <6315@watdcsu.waterloo.edu> campbell@watdcsu.waterloo.edu (Colin Campbell [DCS]) writes:
>In article <16385@watdragon.waterloo.edu> leung@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.