Algorithm to generate (not quite) spanning set in Python with no set longer than 5

Question

Follows on from this question Algorithm to generate (not quite) spanning set in Python

Given n items in a list, for example n = 7, so this input: [1,2,3,4,5,6,7]

I'd like to generate this set of sets in python:

[1] [2] [3] [4] [5] [6] [7]
[1] [2] [3] [4] [5] [6, 7]
[1] [2] [3] [4] [5, 6, 7]
...
...
[1, 2, 3, 4, 5] [6, 7]

But not:

[1, 2, 3, 4, 5, 6] [7]
or
[1, 2, 3, 4, 5, 6, 7]

From the previous question I have this great answer:

def span(lst):
  yield [lst]
  for i in range(1, len(lst)):
    for x in span(lst[i:]):
      yield [lst[:i]] + x

Is it possible to work within this existing code to produce this more specific output

Thanks

what do you mean by "specific output"? Do you mean you want the exact order, and you want to filter out the first and the last list it produces? — Rusty Rob, Feb 12 '12 at 22:07
Looking to filter out those sets that include subsets with more than 5 units. And by 'specific output' I just meant that it's filtered to exclude those sets with subsets of six or more units. — user1195889, Feb 12 '12 at 22:12

Niklas B. · Accepted Answer · 2012-02-12T22:40:19.617

While you could of course just filter the result of the original function using a comprehension like (s for s in span(lst) if max(len(g) for g in s) <= 5), here I present you a recursive solution that doesn't create the invalid results in the first place:

def span(lst, most=float("inf")):
  if not lst:
    yield []
    return

  for i in range(1, min(len(lst), most) + 1):
    for x in span(lst[i:], most):
      yield [lst[:i]] + x

lst = [1,2,3,4,5,6,7]
n = 5
spannings = list(span(lst, n))         
print '\n'.join(map(str, spannings))

# proof that it produces the correct result
assert sorted(spannings) == sorted(s for s in span_orig(lst) if max(map(len, s)) <= n)
# proof that it produces the same result as the old
# function if called without a second argument
assert sorted(span_orig(lst)) == sorted(span(lst))

The logic is very similar, although we can't make use of the yield [lst] "trick" to avoid having to explicitly state the terminating condition len(lst) == 0. I actually think this is cleaner, overall :)

Note how this is a generalization of the original function: If you don't give it a second argument, it will work the same way the old function did.

Algorithm to generate (not quite) spanning set in Python with no set longer than 5

1 Answers1