(Python) Поиск всех возможных разделов списка списков с учетом ограничения размера для раздела - PullRequest
Новая
       22

(Python) Поиск всех возможных разделов списка списков с учетом ограничения размера для раздела

1 голос
/ 14 марта 2019

Предположим, у меня есть список 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]]]

Я понимаю, что это не удаляет дубликаты и исчерпывает возможные комбинации, на которых я застрял.

Некоторое понимание будет отличным!PS Мне не удалось найти похожие вопросы: /

Ответы [ 2 ]

2 голосов
/ 14 марта 2019

Если все элементы в списке уникальны, то вы можете использовать бит.

Предположим, что k = [a, b, c], длина которого равна 3, тогда есть 2 ^ 3 - 1 = 7 разделов:

если вы используете бит для сжатия a, b, c, будет 

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

Итак, ключ к решению этого вопроса теперь очевиден.

1 голос
/ 14 марта 2019

Я думаю, что это то, что вы хотите (пояснения в комментариях): 

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