Path: utzoo!utgpu!watmath!watcgl!ksbooth
From: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Newsgroups: uw.unix
Subject: Re: Permutation
Message-ID: <11492@watcgl.waterloo.edu>
Date: 15 Sep 89 13:39:18 GMT
References: <16385@watdragon.waterloo.edu> <6315@watdcsu.waterloo.edu>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Distribution: uw
Organization: U. of Waterloo, Ontario
Lines: 17

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.