(Python) 查找受分区大小限制限制的列表列表的所有可能分区

Question

假设我有一个列表 k = [[1,1,1],[2,2],[3],[4]]，大小限制为 c = 4。

然后我想找到 k 主题 ot c 所有可能的分区。理想情况下，结果应该是：

[ {[[1,1,1],[3]], [[2,2], [4]]}, {[[1,1,1],[4]], [[2,2], [3]]}, {[[1,1,1]], [[2,2], [3], [4]]}, ..., {[[1,1,1]], [[2,2]], [[3]], [[4]]} ]

我在上面的示例中使用了集合符号 { }（实际情况是 [ ]），以便更清楚地了解什么是分区，其中每个分区包含组合在一起的列表组。

我实现了以下算法，但我的结果不符合：

def num_item(l):
    flat_l = [item for sublist in l for item in sublist]
    return len(flat_l)

def get_all_possible_partitions(lst, c):
    p_opt = []
    for l in lst:
        p_temp = [l]
        lst_copy = lst.copy()
        lst_copy.remove(l)
        iterations = 0
        while num_item(p_temp) <= c and iterations <= len(lst_copy):
            for l_ in lst_copy:
                iterations += 1
                if num_item(p_temp + [l_]) <= c:
                    p_temp += [l_]
        p_opt += [p_temp]
    return p_opt

运行get_all_possible_partitions(k, 4),我得到：

[[[1, 1, 1], [3]], [[2, 2], [3], [4]], [[3], [1, 1, 1]], [[4], [1, 1, 1]]]

我知道它不会删除重复项并耗尽可能的组合，我一直坚持下去。

有些见解会很棒！ P.S。我没能找到类似的问题：/

Answer 1

如果列表中的所有元素都是唯一的，那么你可以使用位。

设k = [a,b,c]，长度为3，则有2^3 - 1 = 7个分区：

如果用bit来组合a,b,c,就会有

001 -> [c]
010 -> [b]
011 -> [b, c]
100 -> [a]
101 -> [a,c]
110 -> [a,b]
111 -> [a,b,c]

所以，现在解决这个问题的关键是显而易见的。

Answer 2

我想这就是你想要的（评论中的解释）：

# Main function
def get_all_possible_partitions(lst, c):
    yield from _get_all_possible_partitions_rec(lst, c, [False] * len(lst), [])

# Produces partitions recursively
def _get_all_possible_partitions_rec(lst, c, picked, partition):
    # If all elements have been picked it is a complete partition
    if all(picked):
        yield tuple(partition)
    else:
        # Get all possible subsets of unpicked elements
        for subset in _get_all_possible_subsets_rec(lst, c, picked, [], 0):
            # Add the subset to the partition
            partition.append(subset)
            # Generate all partitions that complete the current one
            yield from _get_all_possible_partitions_rec(lst, c, picked, partition)
            # Remove the subset from the partition
            partition.pop()

# Produces all possible subsets of unpicked elements
def _get_all_possible_subsets_rec(lst, c, picked, current, idx):
    # If we have gone over all elements finish
    if idx >= len(lst): return
    # If the current element is available and fits in the subset
    if not picked[idx] and len(lst[idx]) <= c:
        # Mark it as picked
        picked[idx] = True
        # Add it to the subset
        current.append(lst[idx])
        # Generate the subset
        yield tuple(current)
        # Generate all possible subsets extending this one
        yield from _get_all_possible_subsets_rec(lst, c - len(lst[idx]), picked, current, idx + 1)
        # Remove current element
        current.pop()
        # Unmark as picked
        picked[idx] = False
    # Only allow skip if it is not the first available element
    if len(current) > 0 or picked[idx]:
        # Get all subsets resulting from skipping current element
        yield from _get_all_possible_subsets_rec(lst, c, picked, current, idx + 1)

# Test
k = [[1, 1, 1], [2, 2], [3], [4]]
c = 4
partitions = list(get_all_possible_partitions(k, c))
print(*partitions, sep='\n')

输出：

(([1, 1, 1],), ([2, 2],), ([3],), ([4],))
(([1, 1, 1],), ([2, 2],), ([3], [4]))
(([1, 1, 1],), ([2, 2], [3]), ([4],))
(([1, 1, 1],), ([2, 2], [3], [4]))
(([1, 1, 1],), ([2, 2], [4]), ([3],))
(([1, 1, 1], [3]), ([2, 2],), ([4],))
(([1, 1, 1], [3]), ([2, 2], [4]))
(([1, 1, 1], [4]), ([2, 2],), ([3],))
(([1, 1, 1], [4]), ([2, 2], [3]))

Answer 3

注意：这个答案实际上是针对closed linked question.

如果你只想 return 列表的二分，你可以使用 more_iterools.set_partions:

>>> from more_itertools import set_partitions
>>>
>>> def get_bipartions(lst):
...     half_list_len = len(lst) // 2
...     if len(lst) % 2 == 0:
...         return list(
...             map(tuple, [
...                 p
...                 for p in set_partitions(lst, k=2)
...                 if half_list_len == len(p[0])
...             ]))
...     else:
...         return list(
...             map(tuple, [
...                 p
...                 for p in set_partitions(lst, k=2)
...                 if abs(half_list_len - len(p[0])) < 1
...             ]))
...
>>> get_bipartions(['A', 'B', 'C'])
[(['A'], ['B', 'C']), (['B'], ['A', 'C'])]
>>> get_bipartions(['A', 'B', 'C', 'D'])
[(['A', 'B'], ['C', 'D']), (['B', 'C'], ['A', 'D']), (['A', 'C'], ['B', 'D'])]
>>> get_bipartions(['A', 'B', 'C', 'D', 'E'])
[(['A', 'B'], ['C', 'D', 'E']), (['B', 'C'], ['A', 'D', 'E']), (['A', 'C'], ['B', 'D', 'E']), (['C', 'D'], ['A', 'B', 'E']), (['B', 'D'], ['A', 'C', 'E']), (['A', 'D'], ['B', 'C', 'E'])]

(Python) 查找受分区大小限制限制的列表列表的所有可能分区

(Python) Finding all possible partitions of a list of lists subject to a size limit for a partition

algorithm

combinations

partitioning

list

python-3.x