Production of all groups of combinations of fixed length
I am looking for an algorithm and / or Python code to generate all possible ways to split a set of elements n
into zero or more groups of elements r
and the remainder. For example, given the set:
[1,2,3,4,5]
with n = 5
and r = 2
, I would like to get
((1,2,3,4,5),) ((1,2),(3,4,5)) ((1,3),(2,4,5)) ... ((1,2),(3,4),(5,)) ((1,2),(3,5),(4,)) ...
In other words, the result of extracting 0 groups from two elements from the set plus the results of extracting 1 group from two elements from the set, as well as the results of extracting 2 groups from two from the set, ... if there n
were more, it would continue.
The order in which these results are generated is irrelevant, and none of them is the order of the elements within each individual group, nor the order of the groups in the result. (e.g., ((1,3),(2,4,5))
equivalent ((3,1),(4,5,2))
, and ((2,5,4),(1,3))
etc.). What I am looking for is that each individual result is obtained at least once, preferably exactly once, in the most efficient way possible.
The brute force method is to generate all possible combinations r
of elements n
, and then create all possible groups of any number of these combinations ( powerset ), iterate over them and process only those in which the combinations in the group have no elements in common. It takes too long even for a small number of elements (it requires iterating over groups of 2 ^ (n! / R! (Nr)!), So the complexity is two-exponential).
Based on the code given in this question , which is essentially a special case for r = 2
and n
even, I came up with the following
def distinct_combination_groups(iterable, r):
tpl = tuple(iterable)
yield (tpl,)
if len(tpl) > r:
for c in combinations(tpl, r):
for g in distinct_combination_groups(set(tpl) - set(c), r):
yield ((c,) + g)
which seems to generate all possible results, but includes some duplicates, a non-trivial number of them when n
quite large. So I am hoping for an algorithm that avoids duplicates.
source to share
How about this?
from itertools import combinations
def partitions(s, r):
"""
Generate partitions of the iterable `s` into subsets of size `r`.
>>> list(partitions(set(range(4)), 2))
[((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
"""
s = set(s)
assert(len(s) % r == 0)
if len(s) == 0:
yield ()
return
first = next(iter(s))
rest = s.difference((first,))
for c in combinations(rest, r - 1):
first_subset = (first,) + c
for p in partitions(rest.difference(c), r):
yield (first_subset,) + p
def partitions_with_remainder(s, r):
"""
Generate partitions of the iterable `s` into subsets of size
`r` plus a remainder.
>>> list(partitions_with_remainder(range(4), 2))
[((0, 1, 2, 3),), ((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
>>> list(partitions_with_remainder(range(3), 2))
[((0, 1, 2),), ((1, 2), (0,)), ((0, 2), (1,)), ((0, 1), (2,))]
"""
s = set(s)
for n in xrange(len(s), -1, -r): # n is size of remainder.
if n == 0:
for p in partitions(s, r):
yield p
elif n != r:
for remainder in combinations(s, n):
for p in partitions(s.difference(remainder), r):
yield p + (remainder,)
Example from OP:
>>> pprint(list(partitions_with_remainder(range(1, 6), 2)))
[((1, 2, 3, 4, 5),),
((4, 5), (1, 2, 3)),
((3, 5), (1, 2, 4)),
((3, 4), (1, 2, 5)),
((2, 5), (1, 3, 4)),
((2, 4), (1, 3, 5)),
((2, 3), (1, 4, 5)),
((1, 5), (2, 3, 4)),
((1, 4), (2, 3, 5)),
((1, 3), (2, 4, 5)),
((1, 2), (3, 4, 5)),
((2, 3), (4, 5), (1,)),
((2, 4), (3, 5), (1,)),
((2, 5), (3, 4), (1,)),
((1, 3), (4, 5), (2,)),
((1, 4), (3, 5), (2,)),
((1, 5), (3, 4), (2,)),
((1, 2), (4, 5), (3,)),
((1, 4), (2, 5), (3,)),
((1, 5), (2, 4), (3,)),
((1, 2), (3, 5), (4,)),
((1, 3), (2, 5), (4,)),
((1, 5), (2, 3), (4,)),
((1, 2), (3, 4), (5,)),
((1, 3), (2, 4), (5,)),
((1, 4), (2, 3), (5,))]
source to share