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

What about this? I haven't tested it yet, but I'll try it later…

I think this technique is called Dynamic Programming:

1. Take the first element [1]
   What can you create with it? Only [1]

2. Take the second one [2]
   Now you've got two possibilities: [1,2] and [1] [2]

3. Take the third one [3]
   With the first of number 2 [1,2] one can create [1,2,3] and [1,2] [3]
   With the second of number 2 [1] [2] one can create [1,3] [2] and [1] [2,3] and [1] [2] [3]

I hope it is clear enough what I tried to show. (If not, drop a comment!)

Answer 2

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]

Answer 3

Here's The SUNY algorithm repository page on the problem. Maybe you can translate one of the code references to python.

Edit: This was a similar problem. Here is the SUNY repository page about generating partitions, which I believe is the correct problem.

Answer 4

The result sets together with the empty set {} looks like the results of the powerset (or power set), but it is not the same thing.

I started a post about a similar problem which has a few implementations (although in C#) and geared more for speed than clarity in some cases. The first example should be easy to translate. Maybe it will give a few ideas anyway.

They work on the principle that emmumerating the combinations is similar to counting in binary (imagine counting from 0 to 16). You do not state if the order is important, or just generating all the combinations, so a quick tidy up may be in order afterwards.

Have a look here (ignore the odd title, the discussion took another direction)

Answer 5

I think the following method is the best way to generate them for the euler problem, as you can replace the return value with the number of prime spanning subsets, and it will be trivial to do the multiplication (especially with memoization):

GenerateSubsets(list)
    partitions = { x | x is subset of list and x contains the lowest element of list }
    foreach (parition in partitions)
        if set == list
            yield { partition }
        else
            yield { partition } x GenerateSubsets(list - part)

The key part is to make sure that the recursive side always has the leftmost element, this way, you don't get duplicates.

I have some messy C# code that does this:

    IEnumerable<IEnumerable<List<int>>> GenerateSubsets(List<int> list)
    {
        int p = (1 << (list.Count)) - 2;
        List<int> lhs = new List<int>();
        List<int> rhs = new List<int>();
        while (p >= 0)
        {
            for (int i = 0; i < list.Count; i++)
                if ((p & (1 << i)) == 0)
                    lhs.Add(list[i]);
                else
                    rhs.Add(list[i]);

            if (rhs.Count > 0)
                foreach (var rhsSubset in GenerateSubsets(rhs))
                    yield return Combine(lhs, rhsSubset);
            else
                yield return Combine(lhs, null);

            lhs.Clear();
            rhs.Clear();
            p -= 2;
        }
    }

    IEnumerable<List<int>> Combine(List<int> list, IEnumerable<List<int>> rest)
    {
        yield return list;
        if (rest != null)
            foreach (List<int> x in rest)
                yield return x;
    }