Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!leah!rpi!crdgw1!ge-dab!peora!ucf-cs!ucf-cs.ucf.edu!vanb
From: vanb@ucf-cs.ucf.edu
Newsgroups: comp.lang.c
Subject: Re: A permutations producing algorithm
Message-ID: <2400006@ucf-cs.ucf.edu>
Date: 24 Jul 89 21:47:00 GMT
References: <1392@umiami.miami.edu>
Lines: 98
Nf-ID: #R:umiami.miami.edu:-139200:ucf-cs.ucf.edu:2400006:000:2836
Nf-From: ucf-cs.ucf.edu!vanb    Jul 24 17:47:00 1989


The following is the simplest way (coding-wise) I know of to code the
'all combinations' problem:

#define NVARS   ??         /* The number of variables                        */
#define MAXVALS ??         /* The maksimum number of values for any variable */
                           /* (Please forgive the spelling - I'm having      */
                           /*  trouble with my 'eks' key.                    */

int values[NVARS][MAVALS]; /* values[i][j] is the jth value of variable i    */
int nvals[NVARS];          /* nvals[i] is the number of values of variable i */
int vector[NVARS];         /* this is a vector of chosen values we're        */
                           /* going to build. vector[i] is the value chosen  */
                           /* from variable i.                               */

void main( void )
{
  /*  Read in or calculate 'values' and 'nvals'  */

  choosem( 0 );
}

void choosem( int level )
{
  int i, j;
  if( level == NVARS )
  {
     /* Do whatever you need to do with the vector  */
  }
  else
  {
    for( i=0; i<nvals[level]; i++ )
    {
      /*  Optional redundancy check - check previous levels */
      for( j=0; j<level; j++) if( vector[j] == values[level][i] ) break;
      if( j==level )  /* If not redundant ... */
      {
        /* These two lines are all you need within the for loop if you */
        /* don't need the redundancy check.                            */
        vector[level] = values[level][i];
        choosem(level+1);
      }
    }
  }
}

If all the variables have the same range of values, then the redundancy
check can be simplified with a global array which indicates whether
a value has been 'used' or not. The following is a simplified version
of the above algorithm which produces all permutations of a list of numbers
using the concept of a 'used' array:

#define NVALS ??    /* Number of values */

int values[NVALS];  /*  Values */
int used[NVALS];    /*  'used' array  */
int vector[NVALS];  /*  Vector - same as before */

void main(void)
{
  int i;
  /* Read in or calculate values */

  for( i=0; i<NVALS; i++ ) used[i] = 0;  /* Nothing is used yet! */
  choosem( 0 );

}

void choosem( int level )
{
  int i;
  if( level == NVALS )
  {
    /*  Do whatever with vector  */
  }
  else
  {
    for( i=0; i<NVALS; i++ ) if( !used[i] )
    {
      used[i] = 1;
      vector[level] = values[i];
      choosem(level+1);
      used[i] = 0;
    }
  }
}

These two algorithms may be used in tandem to solve the problem you specified,
by using the second to produce all permutations of the variables and
the first to generate all combinations of values for a given permutation
of the variables.

There may be more efficient algorithms than this, but this is the simplest
way I know of to simply get it into code.

Hope this stuff is useful ...

vanb