[comp.lang.c] number producing algorithm

baileyc@boulder.Colorado.EDU (BAILEY CHRISTOPHER R) (04/08/90)

Help!  I need an algorithm to generate a series of numbers.  This series is
of variable length.  For example, if I pass a 10 to the function, it needs
to generate numbers that have 10 digits.  The catch is that the numbers it
generates can not have more than one of the same digit, so say, the passed
number is 3, it would generate the following:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

So, basically, there are n! number of combinations/permutations (whichever
it is).  Also, I would like it to start with 0 1 2 ...  Right now, my 
function just creates all numbers by counting in the base of the number that
is passed (in this case base 3), then it checks to see if there are more
than one of the same digit in the number, if so it throws it out.  This is
being used to create node mappings for multipath graphs.  My function is not
good because it takes forever when you get up to >6 nodes.  Thanks!
Chris Bailey :: baileyc@tramp.Colorado.EDU
One Agro Mountain Biker - Dialed in for ultra gonzo badness!
"No his mind is not for rent, to any god or government" - RUSH
Member of Team Buck Naked of Buckingham Palace

davies@sp20.csrd.uiuc.edu (James R. B. Davies) (04/10/90)

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');
   }

dfoster@jarthur.Claremont.EDU (Derek R. Foster) (04/14/90)

In article <19416@boulder.Colorado.EDU> baileyc@tramp.Colorado.EDU (BAILEY CHRISTOPHER R) writes:
>Help!  I need an algorithm to generate a series of numbers.  This series is
>of variable length.  For example, if I pass a 10 to the function, it needs
>to generate numbers that have 10 digits.  The catch is that the numbers it
>generates can not have more than one of the same digit, so say, the passed
>number is 3, it would generate the following:
>
>0 1 2
>0 2 1
>1 0 2
>1 2 0
>2 0 1
>2 1 0
>
>So, basically, there are n! number of combinations/permutations (whichever
>it is).  Also, I would like it to start with 0 1 2 ... 

This was a fun one to do. I like little challenges like this; they're
a like crossword puzzles. I found a reasonably nice solution to it.
It seems to work OK, although you might be able to eliminate the
recursion with a little massaging.
Try this:

#include <stdio.h>

void recurse(int *numlist, int num, int maxnum)
{
  int i,j,norepeats;

  if (num >= maxnum)
  {
    for (j=0; j<maxnum; j++)
      printf("%d ", numlist[j]);
    printf("\n");
    fflush(stdout);
  }
  else
    for (i=0; i<maxnum; i++)
    {
      for (j=0,norepeats=1; j<num && (norepeats=(numlist[j] != i)); j++);
      if (norepeats)
      {
        numlist[num] = i;
        recurse(numlist, num+1, maxnum);
      }
    }
}



void generatelist(int num)
{
  int * numlist;

  numlist = (int *) malloc(sizeof(int) * num);

  recurse(numlist, 0, num);

  free(numlist);
}


void main(void)
{
  int num;

  printf("Enter number?");
  scanf("%d", &num);
  generatelist(num);
}


I hope this is what you wanted!

Derek Riippa Foster