Algorithm for enumerating permutations/combinations
auriocus
some weeks ago a friend asked me, if it is possible somehow, to enumerate all
possible permutations of some given values in Excel. Since I don't have/use
Excel, I could not help him this way, though I cannot imagine this can be done
in a simple way with a spreadsheet program. However, I helped him finally by
writing an awk program that commutes the numbers 1 to 6 and outputs it in a form
that Excel can handle (csv).
This first attempt was intended to be a quick hack and therefore much simple:
Six nested for loops, and the inner loop checked for double elements. Of course
this scales quite poorly. After the job was done, I thought a bit more about
this problem, and found a non-recursive algorithm to the problem, which is
slightly modified suitable for enumerating all k-from-n permutations or
combinations of the numbers 1..n.
The basic idea behind this algorithm is, that there is an index j that
loops over the numbers i[1..n] using the following rules:
* if there could be found a number for i[j], that is not in use (read from a
second array a[i]), then set i[j] to that number, mark it as "used" in a and
increment j
* if there cannot be found such a number, decrement j
* if j==k then print the combination and decrement j
* with changing i[j], also free the entry in a accordingly
* if j reaches zero, then stop
Depending on whether one wants to list the combinations (where the order doesn't
matter) or the permutations, the first valid try for a number is either 1 (perm)
or 1 more than the preceeding number (comb)
These algorithms (in awk) are remarkably faster than the first, dumb version. I
now want to compare it to known algorithms of that problem. Naturally I don't
expect having found the best solution :-) so I want to know, if these algorithms
are wellknown in this form, and if there are better ones.
Here comes the full implementation:
Permutations
#!/bin/awk -f
#
BEGIN {
ORS=""
if (!n) n=5
if ((!k) || (k>n)) k=n
for (j=1; j<=n; j++) {
a[j]=0
i[j]=0
}
a[n+1]=0 /* n+1 is always free */
/* initialize the selected field with 0 */
j=1
while (j!=0) {
s=i[j]
if (s==0) i[j]=1
while (a[i[j]]) i[j]++
if (i[j]==n+1) {
i[j]=0
a[s]=0
j--
continue
}
if (s!=0) a[s]=0
a[i[j]]=1
if (j==k) {
for (l=1; l<k; l++) print i[l] ", "
print i[k] "\n"
continue
}
j++
}
}
Combinations
#!/bin/awk -f
#
BEGIN {
ORS=""
if (!n) n=5
if ((!k) || (k>n)) k=n
for (j=1; j<=n; j++) {
a[j]=0
i[j]=0
}
a[n+1]=0 /* n+1 is always free */
i[0]=0 /* this is for initialising i[1] correctly */
/* initialize the selected field with 0 */
j=1
while (j!=0) {
s=i[j]
if (s==0) i[j]=i[j-1]+1
while (a[i[j]]) i[j]++
if (i[j]==n+1) {
i[j]=0
a[s]=0
j--
continue
}
if (s!=0) a[s]=0
a[i[j]]=1
if (j==k) {
for (l=1; l<k; l++) print i[l] ", "
print i[k] "\n"
continue
}
j++
}
}
These can be run for instance by awk -f permutations.awk -v k=3 -v n=5
Have fun ...
Christian Gollwitzer
Joseph Seigh
auriocus wrote:
>
> Hi all,
>
> some weeks ago a friend asked me, if it is possible somehow, to enumerate all
> possible permutations of some given values in Excel. Since I don't have/use
> Excel, I could not help him this way, though I cannot imagine this can be done
> in a simple way with a spreadsheet program. However, I helped him finally by
> writing an awk program that commutes the numbers 1 to 6 and outputs it in a form
> that Excel can handle (csv).
>
...
I know there are sever books out there on combinatorial algorithms. I've done it
"recursively" using rotational shift of an array. It's probably can be made tailess
so you could then make it iterative if you wanted to.
int x[N] = {....}; // array of size N
permute(int x[], int offset, int size)
for (j = offset; j < size; j++) {
rotate(x, offset, size, 1); // rotate sub array[offset..size] by 1
if (offset < (size - 1))
permute(x, offset + 1, size); // permute next sub array if gt 1 element
else
print(x); // print array
}
}
main:
permute(x, 0, N);
That's the general idea anyhow.
Joe Seigh