leung@gwchem.waterloo.edu (K.W. Leung) (09/14/89)
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
campbell@watdcsu.waterloo.edu (Colin Campbell [DCS]) (09/14/89)
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]]
ksbooth@watcgl.waterloo.edu (Kelly Booth) (09/15/89)
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.