[comp.lang.c] Permutations

leung@gwchem.waterloo.edu (K.W. Leung) (09/16/89)

I have seen sombody post a question on finding permutations of numbers
I've found this particular algorithm in an issue of 1964 
communication of ACM. This is just an direct translation of that alg.
to C. I'm working on another version. I only run the following test
and it seems that it is working quite nicely.

Permutation is actually a hard problem. For people we are interested in
more elegant alogrithm, I know that there is a recent doctoral
dissertation at University of Victoria, BC, Canada. which contain on
elegant alg. on permutation.

===============================CUTABOUTHERE==============================

#include <stdio.h>

void prmut();
void permutation();
int xx[10], kk[10];

main()
{
	int j;

	xx[1] = 1;
	xx[2] = 2;
	xx[3] = 3;
	kk[1] = 2;
	kk[2] = 2;
	kk[3] = 2;
	j = 3;
	prmut(j);
} /* end - main */

void prmut(pp)
int pp;

{
	int x, j, n, m, i, b[10];

	j = pp;

	if ( j==1 ) {
		x = xx[1];
		m = 0;
		goto label1;
	}
	x = xx[j-1];
	m = kk[j-1];
label1:	for ( i=1; i <= kk[j]; i++ )
		b[i] = xx[j];
	permutation(x,m,kk[j], j, b);
} /* end - prmut */

void permutation(x,m,n,j,b)

int x, m, n, j, b[10];

{
	int i, k, n1, n2, j1, a, jj[10], yy[100];

	n2 = n + m;
	if ( m == 0 ) goto label1;
	for ( i=n+1; i <= n2; i++ ) yy[i] = x;
label1:	for ( i=1; i <= n; i++ ) jj[i] = i;
	jj[n+1] = n2+1;
	j1 = j-1;
	k = n;
label2:	for ( i=1; i <= k; i++ ) yy[jj[i]] = b[i];
	if ( j1 <= 1 ) {
		printf("list %d %d %d %d %d %d\n",yy[1],yy[2],yy[3],yy[4],yy[5],yy[6]);
		goto label3;
	}
	a = xx[j1-1];
	n1 = kk[j1-1];
	permutation(a,n1,n2,j1,yy);
label3:	for ( i=1; i <= n; i++ ) {
		yy[jj[i]] = x;
		jj[i] = jj[i] + 1;
		if ( (jj[i] - jj[i+1] + 1) <= 0 )
			goto label4;
		else
			goto label5;
label4:		k = i;
		goto label2;
label5:		jj[i] = i;
	}
} /* end - permutation */