Combination generator

Factual Questions
1

This is not, repeat not, a homework problem.

I am looking for a way to generate a table of coefficients for a program I am working on, such that the significance of the table is the order of the coefficients. As an example, say I start with an array {4, 3, 2, 1, 0}. In the process of ordering the array to {0, 1, 2, 3, 4}, I get every possible intermediate order combination.

I made a half assed attempt to do this with a bubble sort, but when the program was over, I had about a dozen or so intermediates (didn’t count), when I was expecting 120 (5!).

Any help out there, either with a walk through of the algorithm, or maybe even a code snippet?

2

For n = 0 to 4
For m = 0 to 4
if m<> n then for a = 0 to 4
if (m<>a and n<>a) then for b = 0 to 4
if (m<>b and n<>b and a <>b) then for c = 0 to 4
If c<>n and c<>m and c<>a and c<>b) then
print n,m,a,b,c

Brute force and not exactly scalable.

3

Thanks. I’ll play with that.

4

Are you using Python?

If yes it’s easy.



import itertools as it

n = 5

for perm in it.permutations(range(n)):
    print(perm)

Even if you’re not using Python you can look up how it’s done in the itertools documentation.



def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool* for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles* -= 1
            if cycles* == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles* = n - i
            else:
                j = cycles*
                indices*, indices[-j] = indices[-j], indices*
                yield tuple(pool* for i in indices[:r])
                break
        else:
            return