A list of elements is given. I want to have all the possibilities to divide this list into any number of partitions so that each partition has at least x elements. The order of the partitions in the list and the order of the elements in the partition do not matter. E.g.: List = [1,2,3,4] get_partitions(list,2) should return:
[[1,2,3,4],
[[1,2],[3,4]],
[[1,3],[2,4]],
[[1,4],[2,3]]]
List = [1,2,3,4] get_partitions(list,1) should return:
[[1,2,3,4],
[[1,2],[3,4]],
[[1,3],[2,4]],
[[1,4],[2,3]],
[[1],[2],[3,4],
...]
I have started to implement this recursively in Python, but I create too many redundant cases. For runtime reasons, I would like to reduce these cases in advance and not delete them afterwards with frozensets, for example.
from itertools import combinations
import numpy as np
def get_partitions(liste,min,max=None):
if max is None:
# Default setting
max = len(liste)
if len(liste) == min :
# Termination Criterium
yield [liste]
else:
for r in range(np.min([len(liste),max]),min-1,-1):
# max for avoiding cases like: [[1,2,3,4],[2,6]] and [[2,6],[1,2,3,4]]
for perm in combinations(liste,r):
rest = [i for i in liste if i not in perm]
if len(rest) >= min:
for recurse in get_partitions(rest,min,r):
yield [list(perm)] + list(recurse)
if len(rest) == 0:
# r == len(liste)
yield [list(perm)]
This leads to:
[[[1, 2, 3, 4]],
[[1, 2], [3, 4]],
[[1, 3], [2, 4]],
[[1, 4], [2, 3]],
[[2, 3], [1, 4]],
[[2, 4], [1, 3]],
[[3, 4], [1, 2]]]
Thanks in advance for any help.
Trying to use @mozway 's answer and extending it to a recursive version lead me to:
def get_partitions(iterable, minl=2):
s = set(iterable)
for r in range(minl, len(s)//2+1):
if len(s)//2 != r:
for c in combinations(s, r):
for recurse in get_partitions(list(s.difference(c)), minl):
yield [list(c),*recurse]
else:
for c in islice(combinations(s, r), comb(len(s),r)//2):
for recurse in get_partitions(list(s.difference(c)), minl):
yield [list(c),*recurse]
yield [list(s)]
For the example list = [1,2,3,4], x=1 it is reducing the number of possibilities from 47 (my initial try) to 19. Still, there are plenty of redundant cases.
[[[1], [2], [3], [4]], <----
[[1], [2], [3, 4]],
[[1], [2, 3, 4]],
[[2], [1], [3], [4]], <----
[[2], [1], [3, 4]],
[[2], [1, 3, 4]],
[[3], [1], [2], [4]], <----
[[3], [1], [2, 4]],
[[3], [1, 2, 4]],
[[4], [1], [2], [3]], <----
[[4], [1], [2, 3]],
[[4], [1, 2, 3]],
[[1, 2], [3], [4]],
[[1, 2], [3, 4]],
[[1, 3], [2], [4]],
[[1, 3], [2, 4]],
[[1, 4], [2], [3]],
[[1, 4], [2, 3]],
[[1, 2, 3, 4]]]
Here is one long-ish solution. No rejection is used in generating partitions, so in that sense this may be somewhat efficient. Still, there are lots of things to optimize.
Example:
list(get_partitions(range(3), 1))
# [[[0, 1, 2]], [[0], [1, 2]], [[1], [0, 2]], [[2], [0, 1]], [[0], [1], [2]]]
Here is an outline of how this works:
split function that takes a list lst and an integer n and return all ways to split the list into two groups, one of size n and another of size len(lst) - n.lst into n groups each of size k. Of course, this is only possible when len(lst) = n * k. This is implemented in get_partitions_same_size function. The idea is to always include the first element of lst in the first group and recurse.len(lst). I copied code from this thread.p of len(lst), we need to find all ways to partition lst according to p.
len(lst) == 7 and p = 3 + 2 + 2. In this case, we can choose any three elements for the first group, any remaining two for the second group, and there is no choice to be made for the final third group.p corresponds to p_scheme = [(3, 1), (2, 2)]. The function get_partitions_helper takes in a list lst and a "partition scheme" p_scheme, and returns all corresponding partitions without double-counting. This is where get_partitions_same_size from step two is used.get_partitions: we loop over integer partitions of len(lst) and return all possible list partitions corresponding to each possible integer partition.This is a fun problem and comments on bugs and optimizations are very welcome.
from itertools import combinations
from collections import Counter
# from this thread:
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning
def partitions(n, I=1):
yield (n,)
for i in range(I, n//2 + 1):
for p in partitions(n-i, i):
yield (i,) + p
def split(lst, n):
'''
return all ways to split lst into two groups,
with n and len(lst) - n elements respectively
'''
assert len(lst) >= n
# handle special case of len(lst) == 2 * n
if len(lst) == 2 * n:
for first, second in split(lst[1:], n-1):
yield [lst[0], *first], second
else:
for comb in combinations(range(len(lst)), n):
comb = set(comb)
first = [x for i, x in enumerate(lst) if i in comb]
second = [x for i, x in enumerate(lst) if i not in comb]
yield first, second
def get_partitions_same_size(lst, n, k):
# print(lst, n, k)
'return all ways to partition lst into n parts each of size k up to order'
if len(lst) != n * k:
print(lst, n, k)
assert len(lst) == n * k
if n == 0 and len(lst) == 0:
yield []
# case when group size is one
elif k == 1:
yield [[x] for x in lst]
# otherwise, without loss, the first element of lst goes into the first group
else:
for first, rest in split(lst[1:], k-1):
for rec_call in get_partitions_same_size(rest, n-1, k):
yield [[lst[0], *first], *rec_call]
def get_partitions_helper(lst, p_scheme):
"""
return all ways to partition lst into groups according to a partition scheme p_scheme
p_scheme describes an integer partition of len(lst)
for example, if len(lst) == 5, then possible integer partitions are:
[(5,), (1, 4), (1, 1, 3), (1, 1, 1, 2), (1, 1, 1, 1, 1), (1, 2, 2), (2, 3)]
for each, we count the number of groups of a given size
the corresponding partition schemes are:
[[(5, 1)],
[(1, 1), (4, 1)],
[(1, 2), (3, 1)],
[(1, 3), (2, 1)],
[(1, 5)],
[(1, 1), (2, 2)],
[(2, 1), (3, 1)]]
"""
if not lst and not p_scheme:
yield []
return
assert len(lst) == sum(a * b for a, b in p_scheme)
group_size, group_count = p_scheme[0]
num_elts = group_size * group_count
for first, second in split(lst, num_elts):
for firsts in get_partitions_same_size(first, group_count, group_size):
for seconds in get_partitions_helper(second, p_scheme[1:]):
yield [*firsts, *seconds]
def get_partitions(lst, min_):
"""
get all partitions of lst into groups s.t. each group has at least min_ elements
up to order (of groups and elements within a group)
"""
for partition in partitions(len(lst), min_):
p_scheme = list(Counter(partition).items())
yield from get_partitions_helper(lst, p_scheme)