🚀 go-pugleaf

In article <By109I.HEt@apollo.hp.com> holbrook@apollo.HP.COM (Alan R. Holbrook) writes:
|Can someone provide me with an algorithm suitable for writing a program
|to dump all possible combinations of 'n' elements taken 'm' at a time?
|That is, given the string 'abcdefghijklmnop', I'd like to be able to produce
|all possible combinations of, say, 'abcde', then of 'abcdf', or of 'cfilnop'
|then 'aceghilmp', etc.  I think you get the idea.

Nice little problem ... ok, here's my (naive) solution, enjoy.

kind regards,

Jos aka jos@and.nl

-----8<-----snip----------snip----------snip----------snip----------snip-----
#include <stdio.h>

#define MAXP 100		/* Any arbitrary value ... */
#define FREE 1			/* Number not used yet */
#define LOCK 0			/* Number used in a prev position */	

int permtab[MAXP];		/* Current permutation */
int locktab[MAXP];		/* Number (not) used table */

void perm(n, k)
int n, k;
{
	int i, j;

	for (i= 0; i < k; i++) {	/* Init first permutaion */
		permtab[i]= i;
		locktab[i]= LOCK;
	}

	for (i= k; i < n; i++)		/* [k ... n-1] are still free */
		locktab[i]= FREE;


	while (i >= 0) {
	/* 
	 * Simply print out the current permutation (n, k)
	 */
		for (i= 0; i < k; i++)
			printf("%4d ", permtab[i]);
		printf("\n");

	/*
	 * Find the rightmost position that can still be incremented,
	 * e.g. in (4,3) and the current permutation 124, we have to
	 * backup to the second position.
	 */
		for (i= k-1; i>= 0; i--) {

			locktab[permtab[i]]= FREE;

			for (j= permtab[i]+1; j < n; j++)
				if (locktab[j] == FREE) {
					locktab[j]= LOCK;
					permtab[i]= j;
					break;
				}
			if (j < n)
				break;
		}
	/*
	 * We found a rightmost position, now fill in
	 * all positions to the right of this one,
	 * e.g. 124 turned into 13x, we just have to
	 * find an unused number for x.
	 * If we didn't find a rightmost position in
	 * the previous loop, we're done.
	 */
		if (i >= 0) 
			for (i++; i < k; i++) 
				for (j= 0; j < n; j++)
					if (locktab[j] == FREE) {
						permtab[i]= j;
						locktab[j]= LOCK;
						break;
					}
	}
}
-----8<-----snip----------snip----------snip----------snip----------snip-----