Algorithm to generate spanning set

Question

Given this input: [1,2,3,4]

I'd like to generate the set of spanning sets:

[1] [2] [3] [4]
[1] [2] [3,4]
[1] [2,3] [4]
[1] [3] [2,4]
[1,2] [3] [4]
[1,3] [2] [4]
[1,4] [2] [3]
[1,2] [3,4]
[1,3] [2,4]
[1,4] [2,3]
[1,2,3] [4]
[1,2,4] [3]
[1,3,4] [2]
[2,3,4] [1]
[1,2,3,4]

Every set has all the elements of the original set, permuted to appear in unique subsets. What is the algorithm that produces these sets? I've tried Python generator functions using choose, permutation, combination, power set, and so on, but can't get the right combination.

20 Jan 2009

This is not a homework question. This is an improved answer I was working on for www.projecteuler.net problem # 118. I already had a slow solution but came up with a better way -- except I could not figure out how to do the spanning set.

I'll post my code when I get back from an Inauguration Party.

21 Jan 2009

This is the eventual algorithm I used:

def spanningsets(items):
    if len(items) == 1:
        yield [items]
    else:
        left_set, last = items[:-1], [items[-1]]
        for cc in spanningsets(left_set):
            yield cc + [last]
            for i,elem in enumerate(cc):
                yield cc[:i] + [elem + last] + cc[i+1:]

@Yuval F: I know how to do a powerset. Here's a straightforward implementation:

def powerset(s) :
    length = len(s)
    for i in xrange(0, 2**length) :
        yield [c for j, c in enumerate(s) if (1 << j) & i]
    return

Answer 1

This should work, though I haven't tested it enough.

def spanningsets(items):
    if not items: return
    if len(items) == 1:
        yield [[items[-1]]]
    else:
        for cc in spanningsets(items[:-1]):
            yield cc + [[items[-1]]]
            for i in range(len(cc)):
                yield cc[:i] + [cc[i] + [items[-1]]] + cc[i+1:]

for sset in spanningsets([1, 2, 3, 4]):
    print ' '.join(map(str, sset))

Output:

[1] [2] [3] [4]
[1, 4] [2] [3]
[1] [2, 4] [3]
[1] [2] [3, 4]
[1, 3] [2] [4]
[1, 3, 4] [2]
[1, 3] [2, 4]
[1] [2, 3] [4]
[1, 4] [2, 3]
[1] [2, 3, 4]
[1, 2] [3] [4]
[1, 2, 4] [3]
[1, 2] [3, 4]
[1, 2, 3] [4]
[1, 2, 3, 4]