Permutations

nPri.C

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main ( int argc, char *argv[] )
{
  int n, r, k;
  n = atoi(argv[1]);  // # of available elements
  k = atoi(argv[2]);  // # of permutation index
  r = atoi(argv[3]);  // # of elements to be selected
  
  int thisdata[n], temp[n], factoradic[n];
  int i, j;

  // Adjust k for r < (n-1)
  //   If r < (n-1) then we want the first r elements
  //   of the k*(n-r)! permutation (by Joshua Ulrich,
  //   not part of the original algorithm).
  if ( r < (n-1) ) {
    // Compute factorial multiplier
    int fmult = 1;
    for (i = 1; i <= (n-r); ++i) {
      fmult = fmult * i;
    }
    // Apply factorial multiplier
    k = k * fmult;
  }

  // Algorithm taken from:
  // http://msdn.microsoft.com/en-us/library/aa302371.aspx

  // Step #1 - Find factoradic of k
  for (j = 1; j <= n; ++j) {
    factoradic[n-j] = k % j;
    //factoradic[n-j] = (long)fmod(k, j);
    k /= j;
  }
  // Step #2 - Convert factoradic to permuatation
  for (i = 0; i < n; ++i) {
    temp[i] = ++factoradic[i];
  }
  // Set right-most element to 1.
  thisdata[n-1] = 1;  
  // Note what's going on here...
  for (i = n-2; i >= 0; --i) {
    thisdata[i] = temp[i];
    for (j = i+1; j < n; ++j) {
      if (thisdata[j] >= thisdata[i])
        ++thisdata[j];
    }
  }
  // Put in zero-based form
  for (i = 0; i < r; ++i) {
    printf( "%i %s", thisdata[i], " " );
    //--thisdata[i];
  }

}