Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!unmvax!pprg.unm.edu!topgun!mustang!nntp-server.caltech.edu!nntp-server.caltech.edu!daveg
From: daveg@near.cs.caltech.edu (Dave Gillespie)
Newsgroups: comp.lang.c
Subject: Re: need good permutaion generator in C
Message-ID: <DAVEG.90Oct22044828@near.cs.caltech.edu>
Date: 22 Oct 90 10:48:28 GMT
References: <11039@hubcap.clemson.edu>
Sender: news@nntp-server.caltech.edu
Organization: California Institute of Technology
Lines: 56
In-Reply-To: grimlok@hubcap.clemson.edu's message of 19 Oct 90 15:15:37 GMT
Nntp-Posting-Host: near.cs.caltech.edu

>>>>> On 19 Oct 90 15:15:37 GMT, grimlok@hubcap.clemson.edu (Mike Percy) said:

> I'm looking for an iterative (not recursive like the ones I already
> know) permutation routine.

Dijkstra's _A Discipline of Programming_ has a nice little next-permutation
algorithm.  Given an input permutation in an array, it changes it to the
lexicographically next permutation.  So you start with "1 2 3" and repeat
the algorithm until you get to "3 2 1".

Dijkstra invents his own language for use in this book, but I'll be brave
and do an off-the-cuff translation to C.  (This will be untested, but
then Dijkstra proudly states in the introduction that his programs were
published untested since they were derived by such rigorous methods.
Hey, guys, let's start a flame war on the merits of that remark!)


#define SWAP(x,y) { int t = x; x = y; y = t; }

/* Increment the permutation in perm[0] ... perm[n-1]. */
void next_perm(int perm[], int n)
{
  int i = n - 2;   /* Index of leftmost element which needs to change. */
  int j = n - 1;   /* Index of element perm[i] will change to. */

  /* Only the tail of elements in decreasing order must change. */
  while (perm[i] >= perm[i+1]) i--;

  /* perm[i] inherits the next-higher value from the tail. */
  while (perm[j] <= perm[i]) j--;

  /* Swap that into position.  Rest of tail is still decreasing. */
  SWAP(perm[i], perm[j]);

  /* Now reverse the tail end-for-end to get increasing order. */
  j = n;
  while (++i < --j)
    SWAP(perm[i], perm[j]);
}


I always thought this was a fine example of the beauty of good
algorithms.  A place for everything, everything in its place.

You can get the program to test if you have reached the last
permutation automatically by changing the first while loop thusly:

  while (perm[i] >= perm[i+1])
    if (--i < 0)
      return DONE;   /* Input was already the last permutation */

								-- Dave
--
Dave Gillespie
  256-80 Caltech Pasadena CA USA 91125
  daveg@csvax.cs.caltech.edu, ...!cit-vax!daveg