# Untitled

By: a guest on Apr 30th, 2012  |  syntax: None  |  size: 0.92 KB  |  hits: 12  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. Algorithm to generate (not quite) spanning set in Python with no set longer than 5
2. [1] [2] [3] [4] [5] [6] [7]
3. [1] [2] [3] [4] [5] [6, 7]
4. [1] [2] [3] [4] [5, 6, 7]
5. ...
6. ...
7. [1, 2, 3, 4, 5] [6, 7]
8.
9. [1, 2, 3, 4, 5, 6] [7]
10. or
11. [1, 2, 3, 4, 5, 6, 7]
12.
13. def span(lst):
14.   yield [lst]
15.   for i in range(1, len(lst)):
16.     for x in span(lst[i:]):
17.       yield [lst[:i]] + x
18.
19. def span(lst, most=float("inf")):
20.   if not lst:
21.     yield []
22.     return
23.
24.   for i in range(1, min(len(lst), most) + 1):
25.     for x in span(lst[i:], most):
26.       yield [lst[:i]] + x
27.
28. lst = [1,2,3,4,5,6,7]
29. n = 5
30. spannings = list(span(lst, n))
31. print 'n'.join(map(str, spannings))
32.
33. # proof that it produces the correct result
34. assert sorted(spannings) == sorted(s for s in span_orig(lst) if max(map(len, s)) <= n)
35. # proof that it produces the same result as the old
36. # function if called without a second argument
37. assert sorted(span_orig(lst)) == sorted(span(lst))