Newsgroups: comp.lang.c
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!brutus.cs.uiuc.edu!ux1.cso.uiuc.edu!sp20.csrd.uiuc.edu!davies
From: davies@sp20.csrd.uiuc.edu (James R. B. Davies)
Subject: Re: number producing algorithm
Message-ID: <1990Apr10.161816.10685@ux1.cso.uiuc.edu>
Sender: usenet@ux1.cso.uiuc.edu (News)
Reply-To: davies@uicsrd.csrd.uiuc.edu
Organization: University of Illinois Center for Supercomputing Research and Development	
References:  <19416@boulder.Colorado.EDU>
Distribution: usa
Date: Tue, 10 Apr 90 16:18:16 GMT


The method I use for producing permutations is pretty simple
conceptually in that it is recursively structured.

permute N digits:
   for each remaining digit
       save this digit
       permute the N-1 remaining digits
   end for
end

The following quick hack does this in C.  It passes the number
of digits to permuted and a bit-mask of available digits
to function "permute".  The current sequence being tried is
kept is external variable "permutation", the total length in
external variable "n_digits".  When the recursion bottoms out,
"report_permutation" is called to print out the result.  Note
that the digits are printed from n_digits-1 down to 0 so that
they come out sorted the way you wanted.  The main program I
provided just calls permute for each number given on the command
line.  The initial mask should have at least as many rightmost bits 
set as the number of digits being permuted.

Thanks for the puzzle!  I enjoy this sort of thing...

							Jim Davies
-------- cut here -------------
#include <stdio.h>

char permutation[10];
int n_digits;
   
main(argc,argv)
int argc; char **argv;
{

   while (--argc) {
      n_digits = atoi(*++argv);
      if (n_digits < 1 || n_digits > 10) exit(0);

      permute(n_digits, 01777);
      putchar('\n');
      }

   }

permute(N,mask)
int N, mask;
{

   int i, new_mask;

   /*printf("permute(%d,0%o)\n",N,mask);*/

   for (i = 0; i < n_digits; i++) {
      if (mask & (1<<i)) {
         permutation[N-1] = '0' + i;
         if (N > 1) {
            new_mask = mask & (~ (1<<i));
            permute(N-1,new_mask);
            }
         else {
            report_permutation();
            }
         }
      }
   }

report_permutation()
{
   int i;
   for (i = n_digits-1; i >= 0; i--) {
      putchar(permutation[i]);
      }
   putchar('\n');
   }