number producing algorithm
James R. B. Davies
davies at sp20.csrd.uiuc.edu
Wed Apr 11 02:18:16 AEST 1990
The method I use for producing permutations is pretty simple
conceptually in that it is recursively structured.
permute N digits:
for each remaining digit
save this digit
permute the N-1 remaining digits
end for
end
The following quick hack does this in C. It passes the number
of digits to permuted and a bit-mask of available digits
to function "permute". The current sequence being tried is
kept is external variable "permutation", the total length in
external variable "n_digits". When the recursion bottoms out,
"report_permutation" is called to print out the result. Note
that the digits are printed from n_digits-1 down to 0 so that
they come out sorted the way you wanted. The main program I
provided just calls permute for each number given on the command
line. The initial mask should have at least as many rightmost bits
set as the number of digits being permuted.
Thanks for the puzzle! I enjoy this sort of thing...
Jim Davies
-------- cut here -------------
#include <stdio.h>
char permutation[10];
int n_digits;
main(argc,argv)
int argc; char **argv;
{
while (--argc) {
n_digits = atoi(*++argv);
if (n_digits < 1 || n_digits > 10) exit(0);
permute(n_digits, 01777);
putchar('\n');
}
}
permute(N,mask)
int N, mask;
{
int i, new_mask;
/*printf("permute(%d,0%o)\n",N,mask);*/
for (i = 0; i < n_digits; i++) {
if (mask & (1<<i)) {
permutation[N-1] = '0' + i;
if (N > 1) {
new_mask = mask & (~ (1<<i));
permute(N-1,new_mask);
}
else {
report_permutation();
}
}
}
}
report_permutation()
{
int i;
for (i = n_digits-1; i >= 0; i--) {
putchar(permutation[i]);
}
putchar('\n');
}
More information about the Comp.lang.c
mailing list