🚀 go-pugleaf

In article <1993Jan6.014749.15323@ee.ubc.ca> rayw@ee.ubc.ca (raymond w m woo) writes:
>Hi, does anyone know, or can provide any pointer in the literature to, any 
>random permutation generation algorithm that can be easily implemented as a 
>function in a computer program?  
>
>Ideally, this function would be computationally effective, and the input 
>that this function takes would be some kind of index/rank number of the
>permution to be generated.  

then karr@cs.cornell.edu (David Karr) describes an alg

>Now for b = N down to 2, take i = k mod b.  Copy v[i] to w[p],
>increment p, copy v[t] to v[i], decrement t.  Essentially this has
>just removed the i-th element of v, adding it to the output and
>shrinking v accordingly.

Additionally one should (integer) divide k by b in the loop, 
(i.e. k = k div b) after the computation of i.

Follows is a quickly written C++ program for this, that has been tested
to be correct (provide a unique permutation for each index)
for all permutations up to and including rank 8:

===============================================================================

//permute.C,  a C++ program for computing random permutations

#include <stream.h>

void permute( int rank, int index, int output[] ) {
// returns a permutation of given rank.  
// index is a number between 1 and rank!, corresponding to a unique
// permutation to return

  int i;
  int v[rank];
  // set v = {1234 . . . rank}
  for (i = 0; i<rank;) 
	v[i] = ++i;

  int t = rank-1;
  int p = 0;

  for (int b = rank; b>1; b--) {
	i = index % b;
  	index /= b;
	output[p++] = v[i]; //move v[i] to the output permutation
	v[i] = v[t--];	    //remove v[i] from list of remaining elements
  }
  output[rank-1] = v[0];
}

int fact( int v ) {
  if (v>1) {
    int w = v--;
    for (; v > 1; v--)
	w *= v;
    return w;
  }
  else 
    return 1;
}

void vecset( int dest[], int source[], int rank ) {
//assign dest permutation vector to be equall to source
//vectors are of length rank 
//use memcpy for faster results if you like
	for (int i =0; i<rank; i++) 
	  dest[i] = source[i];
}

int is_same_vec( int v1[], int v2[], int rank ) {
//return true if v1 and v2 are identical vectors of length rank
	for (int i = 0; i<rank; i++)
	  if (v1[i] != v2[i]) return 0;
	return 1;
}

void display( int v1[], int rank ) {
//display a permutation vector on standard output
	for (int i = 0; i<rank; i++) 
	 	cout << v1[i];
  	cout << "\n";
}

main( int argc, char * argv[] ) {
//generate and display permutation vectors, 

  //display all permutation vectors of rank 1..6
  for (int rank = 1; rank < 7; rank++) {
    cout << "\n";  //new line
    int output [rank];  // a particular permutation
    int savoutput[fact(rank)] [rank]; //save all permutation vectors for rank

    //generate and display all permutation vectors of given rank
    for (int k = fact(rank); k>0; k--) {
	permute( rank, k, output );
	vecset(savoutput[k-1], output, rank);
	display( output, rank );
    }

    //test uniqueness of permutation vectors of given rank
    for (int j = 0; j<fact(rank)-1; j++)
      for (int n = j+1; n<fact(rank); n++)
	if (is_same_vec(savoutput[j], savoutput [n], rank)) {
		cout << "error " << n << " " << j 
		<< " rank= " << rank << "\n";
		display( savoutput[j], rank );
		display( savoutput[n], rank );
	}

  }
}