社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

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

Stoner • 6 年前 • 1945 次点击  

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
文章 [ 2 ]  |  最新文章 6 年前
Tim
Reply   •   1 楼
Tim    7 年前

如果列表中的所有元素都是唯一的,则可以使用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]

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

jdehesa
Reply   •   2 楼
jdehesa    7 年前

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

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