From: ressler@cs.cornell.edu (Gene Ressler)
Subject: Re: Permutation generation
Followup-To:  ressler@cs.cornell.edu
Summary: Painless permutations
Keywords: permutations
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Thu, 9 Apr 1992 02:27:43 GMT

In article <1992Apr8.210949.21425@odin.diku.dk> elgaard@diku.dk (Niels Elgaard Larsen) writes:
>jont@cs.su.oz (Jonathon Tidswell) writes:
>
>>Some time ago a series of articles were posted on generating specific
>>permutations.
>>I have a slightly problem.
>>    I want all possible permutations of n numbers ( n known at compile time ).
>>    I dont need more than one permutation at a time.
>>    And calling permutation( array, index, length ) n! times is I think not
>>    optimal.
>>    I did it in recursion, but since I use C, this is painful.
>
>>Has anybody got an iterative solution to this.
>
>I changed the recursive solution, I posted earlier:
>
>/* Permutation of N integers */  ... rest of impressive-looking code omitted. ;-)

Wow. This code looks too hard!

Two comments:  First, you can still handle the problem elegantly with recursion
if you pass a function to be applied to each permutation as an argument.
Second, as is often the case, the recursive solution can be rephrased in a concise
iterative form, though this requires a little more head scratching.

Here are my ideas extracted from old code (I tried to e-mail these
earlier, but the message bounced).

With recursion:

#include <stdio.h>

void swap(int *i, int *j) { int t = *i; *i = *j; *j = t; }

/* Permutation `module'. */

static void (*F)(int*,int);	/* Action function. */
static int *V, N;		/* Vector to permute */

/* Local permuter. */
static void p (int *v, int n)
{
  int i;
  if (n == 0) { (*F)(V, N); return; }
  for (i = 0; i < n; ++i) { swap(v, v+i); p(v+1, n-1); swap(v, v+i); }
}

/* Permute v all n! ways and call `f(v,n)' on each. */
void permute(int *v, int n, void (*f)(int*,int)) { V = v; N = n; F = f; p(v, n); }

/* Caller of module: */

void print(int *v, int n)
{
  while (n > 0) { printf("%d ", *v++); --n; }  printf("\n");
}

void main(int argc, char *argv[])
{
  int i, n, v[100];

  if (argc < 2 || sscanf(argv[1], "%d", &n) < 1) n = 3;
  for (i = 0; i < n; ++i) v[i] = i;
  /* Apply `print' to all permutations of v. */
  permute(v, n, print);
}

Ok, now to get the iterative version, we `bottle' the state of p() in a 
vector s and obtain this code (with less attention to module structure):

#include <stdio.h>

void swap(int *i, int *j) { int t = *i; *i = *j; *j = t; }

static int s[100], v[100], n;

void permute(void)
{
  int i, *p;

  for (i = 1, p = v+1; i < n; ++i, ++p) {
    swap(p, p - s[i]);
    if (++s[i] > i) s[i] = 0;
    swap(p, p - s[i]);
    if (s[i] != 0) break;
  }
}

void main(int argc, char *argv[])
{
  int i, j, f;

  if (argc < 2 || sscanf(argv[1], "%d", &n) < 1) n = 3;

  /* set v to 0,1,... and store n factorial into f. */
  for (i = 0, f = 1; i < n; ++i) { v[i] = i; f *= (i+1); }

  /* Print n!+1 permutations, first == last. */
  for (i = 0; i <= f; ++i) {
    for (j = 0; j < n; ++j) printf("%d ", v[j]); printf("\n");
    permute();
  }
}

Oh, I guess it's worth noting that these require O(n) time to form n
permutations.  If that sounds fishy, see e.g. Sleator and Tarjan's
neat argument for the amortized time bounds on Fibonacci heaps.

Gene
Newsgroups: comp.programming