Блог

У меня есть список возможных вариантов: [[1], [2, 4], [4], [5, 6, 2], [5, 3]] .

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

Так [1, 2, 4, 5, 3] что это допустимый вариант. Но [1, 4, 4, 5, 3] это не так. Я разрешаю не делать выбор ни в одном подсписке, поэтому [1,4, None,5,3] действителен, как в [1, None, None, None, None] , и [None, None, None, None, None] .

Я не могу просто перечислить все комбинации, а затем отфильтровать те, которые мне не нужны, так как для большого списка возможных вариантов это быстро стало бы невозможным с точки зрения вычислений (я смотрю на 25^25 максимальных комбинаций в моем проекте).

редактировать: Я бы также применил некоторые дополнительные критерии к результатам, такие как фильтрация, чтобы иметь не более порога None выбора, или сортировка результирующего списка комбинаций в порядке комбинаций с наименьшим количеством None вариантов.

редактировать: с подробностями реального случая: я хотел бы применить его к списку из 25 подсписков, каждый из которых может содержать 1-25 элементов. В действительности, каждый подсписк будет содержать не более 15 элементов, в среднем 2-4.

Таким образом, простое решение list(itertools.product(*choices)) для последующей фильтрации исключено.

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

Я попытался рекурсивно построить дерево, где, например, корневой узел имеет полный список вариантов, дочерний узел делает первый выбор [1] и имеет обновленный список вариантов, где » 1 » удаляется из всех вариантов списка[1:].

Однако я изо всех сил пытаюсь реализовать рекурсию.

Можете ли вы помочь мне с любыми другими подходами?

Другой способ генерировать все допустимые выходные данные с минимальным использованием памяти-это перебирать элементы, а не списки. Используйте поиск по глубине, чтобы с самого начала генерировать только допустимые выходные данные. Это означает, что нам нужно отслеживать три вещи на каждом уровне нашей DFS: текущий элемент, который можно добавить, списки, которые уже используются, и порядок, в котором мы использовали эти предыдущие списки.

Чтобы помочь в нашем поиске, мы предварительно обрабатываем варианты, сопоставляя каждый элемент набору возможных списков, в которых он может находиться, что создает своего рода Двойную версию проблемы. Это также генерирует списки примерно в порядке «максимального непустого выбора в первую очередь».

Поскольку вы указали, что количество уникальных элементов N равно количеству списков, этот подход выполняется со O(N * |output|) временем, и мы везде используем генераторы для экономии памяти.

 import collections
from typing import Dict, Generator, List, Optional, Set

choices = [[1], [2, 4], [4], [5, 6, 2], [5, 3]]
element_to_containing_lists: Dict[int, Set[int]] = collections.defaultdict(set)

for i, choice_list in enumerate(choices):
    for x in choice_list:
        element_to_containing_lists[x].add(i)

all_unique_elements = sorted(element_to_containing_lists)


def dfs(used_list_indices: Set[int],
        next_element_index: int,
        used_list_ordered_indices: List[Optional[int]]) -> Generator[List[Optional[int]]]:
    if next_element_index == len(all_unique_elements):
        yield used_list_ordered_indices
    else:
        # If we use the element, find an unused list index
        for possible_list_to_use in element_to_containing_lists[
                                        all_unique_elements[next_element_index]] - used_list_indices:
            yield from dfs(used_list_indices | {possible_list_to_use},
                           next_element_index   1,
                           used_list_ordered_indices   [possible_list_to_use])

        # If we don't use the element: Add None as a sentinel value
        yield from dfs(used_list_indices,
                       next_element_index   1,
                       used_list_ordered_indices   [None])


for element_to_used_list in dfs(set(), 0, []):
    list_to_chosen_element = ['N'] * len(choices)
    for x, y in zip(all_unique_elements, element_to_used_list):
        if y is not None:
            list_to_chosen_element[y] = x
    print(*list_to_chosen_element, sep='  ')
 

Первые 10 строк вывода:

 1  2  4  5  3
1  2  4  6  3
1  2  4  N  3
1  2  N  5  3
1  2  N  6  3
1  2  N  N  3
1  2  4  5  N
1  2  4  6  5
1  2  4  N  5
 

Возможно, это можно оптимизировать для выполнения во O(|output|) времени, используя битовую маску для «используемых списков», а не набор их индексов.

Не превращайте результат в список. product это генератор. Используйте это в своих интересах. filter это тоже генератор. Таким образом, вы сохраняете в памяти только одну комбинацию. Иногда один вывод product будет отброшен внутренне без вашего ведома, но он не займет никакого дополнительного места.

 def criterion(x):
    k = [i for i in x if i is not None]
    return len(k) == len(set(k))

choices = [[1], [2, 4], [4], [5, 6, 2], [5, 3]]
for c in choices:
    c.append(None)
filter(criterion, product(*choices))
 

Очень похоже на предыдущий ответ. Не так быстро, но я думаю, что это легче понять. Простая рекурсивная реализация.

 def pick_all(choices):
    # The result on an empty choices list is just a single empty list
    if not choices:
        yield []
        return
    # Pluck off the first choice
    first_choice, *remainder = choices

    # Recursively find all solutions to the smaller problem.
    for result in pick_all(remainder):
        # We can always add None to the front
        yield [None, *result]
        for item in first_choice:
            # And we can add any item in this choice that's not already there.
            if item not in result:
                yield [item, *result]
 

 [set(dataset) for dataset in itertools.product(*datasets)]
 

Создает список комбинаций наборов. Наборы похожи на списки, но автоматически удаляют существующие значения. Этот код не гарантирует, что наборы имеют длину 5. Наборы заметок также неупорядочены.

 print([dataset for dataset in itertools.product(*datasets) if len(set(dataset)) == len(dataset)])
 

Список комбинаций и отфильтровывает любые списки с повторяющимися значениями, убедившись, что набор данных имеет ту же длину, что и исходный список.

 datasets = [[1], [2, 4], [4], [5, 6, 2], [5, 3]]
datasets = [[*dataset, None] for dataset in datasets]

new_dataset = []
for dataset in itertools.product(*datasets):
    without_nones = [n for n in dataset if n is not None]
    if len(without_nones) == len(set(without_nones)):
        new_dataset.append(dataset)

print(new_dataset)
 

Создает список комбинаций, длина которых всегда равна 5, не имеет повторяющихся чисел и может иметь неограниченное количество нулей.

Вероятно, это должен быть генератор, и я подозреваю, что есть более простой способ выполнить все, для чего вам нужен список в этом формате.