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

Stoner • 4 年前 • 573 次点击

k = [[1,1,1],[2,2],[3],[4]] ,有大小限制 c = 4 .

然后我想找到所有可能的分区 k 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、我没有找到类似的问题:/

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/53642

573 次点击

文章 [ 2 ] | 最新文章 4 年前

• 1 楼

Tim 5 年前

如果列表中的所有元素都是唯一的,则可以使用bit。

假设k=[a,b,c],长度为3,则有2^3-1=7个部分:

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

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

• 2 楼

jdehesa 5 年前

我想这就是你想要的(评论中的解释):

# 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]))

登录后回复