Ответ 1

Это не "ответ", как стимул, чтобы думать сложнее ;-) Для конкретности я обернурую код OP, слегка отброшенный, в функцию, которая также уничтожает дубликаты:

def gen(pools, ixs):
    from itertools import combinations_with_replacement as cwr
    from itertools import chain, product
    from collections import Counter

    assert all(0 <= i < len(pools) for i in ixs)
    seen = set()
    cnt = Counter(ixs) # map index to count
    blocks = [cwr(pools[i], count) for i, count in cnt.items()]
    for t in product(*blocks):
        t = tuple(sorted(chain(*t)))
        if t not in seen:
            seen.add(t)
            yield t

Я не боюсь сортировки здесь - он эффективен с точки зрения памяти, а для небольших кортежей, скорее всего, быстрее, чем все накладные расходы, связанные с созданием объекта Counter.

Но независимо от этого, здесь нужно подчеркнуть реальную ценность, которую получил ОП, переформулировав проблему на использование combinations_with_replacement (cwr). Рассмотрим эти данные:

N = 64
pools = [[0, 1]]
ixs = [0] * N

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

pools = [[0, 1]] * N
ixs = range(N)

также имеет те же самые 65 уникальных результатов, но в основном работает навсегда (как, например, другие ответы до сих пор), проваливаясь через 2 ** 64 возможности. cwr здесь не помогает, потому что каждый индекс пула появляется только один раз.

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

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

Один, основанный на ответе @user2357112

Объединение cwr с cwr @user2357112 инкрементного дедупликации дает краткий алгоритм, который выполняется быстро во всех тестовых случаях, которые у меня есть. Например, это по существу мгновенно для обоих описаний примеров [0, 1] ** 64 выше, и приводит пример в конце @Joseph Wood примерно так же быстро, как он сказал, что его код C++ запустился (0,35 секунды мой ящик под Python 3.7.0, и, да, найдено 162295 результатов):

def gen(pools, ixs):
    from itertools import combinations_with_replacement as cwr
    from collections import Counter

    assert all(0 <= i < len(pools) for i in ixs)
    result = {()}
    for i, count in Counter(ixs).items():
        result = {tuple(sorted(old + new))
                  for new in cwr(pools[i], count)
                  for old in result}
    return result

Чтобы упростить другим Pythonistas попробовать последний пример, здесь вход как исполняемый Python:

pools = [[1, 10, 14, 6],
         [7, 2, 4, 8, 3, 11, 12],
         [11, 3, 13, 4, 15, 8, 6, 5],
         [10, 1, 3, 2, 9, 5,  7],
         [1, 5, 10, 3, 8, 14],
         [15, 3, 7, 10, 4, 5, 8, 6],
         [14, 9, 11, 15],
         [7, 6, 13, 14, 10, 11, 9, 4]]
ixs = range(len(pools))

Однако позже OP добавил, что у них обычно около 20 пулов, каждый из которых содержит несколько тысяч элементов. 1000 ** 20 = 1e60 является практически недоступным для любого подхода, который строит полный декартовский продукт, независимо от того, насколько умно он уничтожает дубликаты. Остается ясным, как грязь, сколько они ожидают быть дубликатами, хотя так же ясно, как грязь, является ли такой "постепенный дедупликация" достаточно хорошим, чтобы быть практичным.

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

Ленивое лексикографическое поколение

Исходя из инкрементного устранения дублирования, предположим, что мы имеем строго возрастающую (лексикографическую) последовательность отсортированных кортежей, добавляем один и тот же набор T к каждому и сортируем каждый раз. Тогда производная последовательность все еще находится в строго возрастающем порядке. Например, в левом столбце мы имеем 10 уникальных пар из range(4), а в правом столбце - то, что происходит после добавления (и сортировки) 2 к каждому:

00 002
01 012
02 022
03 023
11 112
12 122
13 123
22 222
23 223
33 233

Они начались в порядке сортировки, и полученные тройки также отсортированы по порядку. Я пропущу простое доказательство (эскиз: если t1 и t2 - соседние кортежи, t1 < t2 и пусть i - наименьший индекс, такой, что t1[i] != t2[i]. Тогда t1[i] < t2[i] (что означает "лексикографический <"). Затем, если вы перебрасываете x в оба кортежа, действуйте по случаям: x <= t1[i]? между t1[i] и t2[i]? x >= t2[i]? В каждом случае легко видеть, что первый производный кортеж остается строго меньше второго производного набора.)

Итак, предположим, что у нас есть отсортированный result последовательности всех уникальных отсортированных кортежей из некоторого количества пулов, что происходит, когда мы добавляем элементы нового пула P в кортежи? Ну, как и выше,

[tuple(sorted(old + (P[0],))) for old in result]

также сортируется, и

[tuple(sorted(old + (P[i],))) for old in result]

для всех i в range(len(P)). Эти гарантированные уже отсортированные последовательности могут быть объединены через heapq.merge(), а другой генератор (killdups() ниже) запускает результат слияния, чтобы отсеять дубликаты "на лету". Там нет необходимости, например, хранить набор всех кортежей, видимых до сих пор. Поскольку вывод слияния не уменьшается, достаточно просто проверить, совпадает ли следующий результат с последним результатом.

Как это лениво работать, это нежно. К тому, что каждый элемент добавляемого нового пула должен получить доступ к всей последовательности результатов до такой степени, мы не хотим материализовать все это одним глотком. Вместо этого itertools.tee() позволяет каждому элементу следующего пула проходить последовательность результата так далеко в своем собственном темпе и автоматически освобождает память для каждого элемента результата после того, как все новые элементы пула закончили с ним.

Функция build1() (или некоторый workalike) необходима для обеспечения доступа к правильным значениям в нужное время. Например, если тело build1() вставлено в inline, где оно было build1(), код не будет эффектно (тело получит доступ к конечным значениям, связанным с rcopy и new а не к тому, к чему они были привязаны во время выражения генератора создано).

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

Техническое примечание: не бойтесь sorted() здесь. Добавление происходит по old + new по какой-то причине: old уже отсортирован, а new обычно является 1-й кортеж. Сорт Python в этом случае является линейным, а не O(N log N).

def gen(pools, ixs):
    from itertools import combinations_with_replacement as cwr
    from itertools import tee
    from collections import Counter
    from heapq import merge

    def killdups(xs):
        last = None
        for x in xs:
            if x != last:
                yield x
                last = x

    def build1(rcopy, new):
        return (tuple(sorted(old + new)) for old in rcopy)

    assert all(0 <= i < len(pools) for i in ixs)
    result = [()]
    for i, count in Counter(ixs).items():
        poolelts = list(cwr(pools[i], count))
        xs = [build1(rcopy, new)
              for rcopy, new in zip(tee(result, len(poolelts)),
                                    poolelts)]
        result = killdups(merge(*xs))
    return result

2 входа

Оказывается, что для случая с 2 входами существует простой подход, полученный из алгебры множеств. Если x и y одинаковы, то cwr(x, 2) является ответом. Если x и y не пересекаются, то product(x, y). Кроме того, пересечение c из x и y непусто, и ответ - это кантация 4 кросс-продуктов, полученных из 3 попарно непересекающихся множеств c, xc и yc: cwr(c, 2), product(xc, c), product(yc, c) и product(xc, yc). Доказательство просто, но утомительно, поэтому я пропущу его. Например, между cwr(c, 2) и product(xc, c) нет дубликатов product(xc, c) потому что каждый кортеж в последнем содержит элемент из xc, но каждый кортеж в первом содержит элементы только из c, а xc и c - не пересекаются по построению. В product(xc, yc) нет дубликатов product(xc, yc) поскольку два входа не пересекаются (если они содержат общий элемент, который был бы на пересечении x и y, что противоречило бы тому, что xc не имеет элемента в пересечении). И т.п.

Увы, я не нашел способ обобщить это за 2 входа, что меня удивило. Его можно использовать самостоятельно или в качестве строительного блока в других подходах. Например, если есть много входов, их можно искать пар с большими пересечениями, и эта схема с двумя входами используется для непосредственного выполнения этих частей общих продуктов.

Даже на 3 входах мне не ясно, как получить правильный результат для

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

Полное декартово произведение имеет 2 ** 3 = 8 элементов, только один из которых повторяется: (1, 2, 3) появляется дважды (как (1, 2, 3) и снова как (2, 3, 1)). Каждая пара входов имеет 1-элементное пересечение, но пересечение всех 3 пусто.

Здесь реализация:

def pair(x, y):
    from itertools import product, chain
    from itertools import combinations_with_replacement
    x = set(x)
    y = set(y)
    c = x & y
    chunks = []
    if c:
        x -= c
        y -= c
        chunks.append(combinations_with_replacement(c, 2))
        if x:
            chunks.append(product(x, c))
        if y:
            chunks.append(product(y, c))
    if x and y:
        chunks.append(product(x, y))
    return chain.from_iterable(chunks)

Доказательство концепции на основе максимального соответствия

Это сочетает идеи из эскиза @Leon и подхода @JosephWoods, очерченного в комментариях. Он не отполирован и, очевидно, может ускоряться, но он достаточно быстро справляется со всеми делами, которые я пробовал. Поскольку он довольно сложный, возможно, более полезно опубликовать его в уже неудовлетворительной, достаточной для всех, не оптимизированной форме!

Это не делает попыток определить набор "свободных" пулов (как в эскизе @Leon). Прежде всего потому, что у меня не было кода, который сидел вокруг, и отчасти потому, что не сразу было ясно, как это сделать эффективно. У меня был код, который сидел вокруг, чтобы найти совпадение на двудольном графике, и в этом контексте потребовалось лишь несколько изменений.

Таким образом, он пытается получить правдоподобные префиксы результата в лексикографическом порядке, как в эскизе @JosephWood, и для каждого видит, можно ли его построить, проверяя, существует ли совпадение двухстороннего графика.

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

def matchgen(pools, ixs):
    from collections import Counter
    from collections import defaultdict
    from itertools import chain, repeat, islice

    elt2pools = defaultdict(set)
    npools = 0
    for i, count in Counter(ixs).items():
        set_indices = set(range(npools, npools + count))
        for elt in pools[i]:
            elt2pools[elt] |= set_indices
        npools += count
    elt2count = {elt : len(ps) for elt, ps in elt2pools.items()}

    cands = sorted(elt2pools.keys())
    ncands = len(cands)

    result = [None] * npools

    # Is it possible to match result[:n] + [elt]*count?
    # We already know it possible to match result[:n], but
    # this code doesn't exploit that.
    def match(n, elt, count):

        def extend(x, seen):
            for y in elt2pools[x]:
                if y not in seen:
                    seen.add(y)
                    if y in y2x:
                        if extend(y2x[y], seen):
                            y2x[y] = x
                            return True
                    else:
                        y2x[y] = x
                        return True
            return False

        y2x = {}
        freexs = []
        # A greedy pass first to grab easy matches.
        for x in chain(islice(result, n), repeat(elt, count)):
            for y in elt2pools[x]:
                if y not in y2x:
                    y2x[y] = x
                    break
            else:
                freexs.append(x)
        # Now do real work.
        seen = set()
        for x in freexs:
            seen.clear()
            if not extend(x, seen):
                return False
        return True

    def inner(i, j): # fill result[j:] with elts from cands[i:]
        if j >= npools:
            yield tuple(result)
            return
        for i in range(i, ncands):
            elt = cands[i]
            # Find the most times 'elt' can be added.
            count = min(elt2count[elt], npools - j)
            while count:
                if match(j, elt, count):
                    break
                count -= 1
            # Since it can be added 'count' times, it can also
            # be added any number of times less than 'count'.
            for k in range(count):
                result[j + k] = elt
            while count:
                yield from inner(i + 1, j + count)
                count -= 1

    return inner(0, 0)

EDIT: обратите внимание, что здесь есть потенциальная ловушка, иллюстрируемая range(10_000) пулов range(10_000) и range(100_000). После производства (9999, 99999) первая позиция увеличивается до 10000, а затем она продолжается очень долго, вызывая, что нет никакой возможности для любой из возможностей в 10001.. 99999 во второй позиции; а затем на 10001 в первой позиции не соответствует ни одной из возможностей в 10002.. 99999 во второй позиции; и так далее. Схема @Leon вместо этого заметила бы, что range(10_000) остался единственным свободным пулом, который собрал 10000 в первой позиции и сразу же отметил, что range(10_000) не содержит значений больше 10000. Очевидно, сделать это снова для 10001, 10002,..., 99999 в первой позиции. Это линейная, а не квадратичная отработка циклов, но все равно отходы. Мораль истории: не доверяйте никому, пока у вас нет реального кода, чтобы попробовать ;-)

И один, основанный на схеме @Leon

Следующее - это более чем верное воплощение идей @Leon. Мне нравится код лучше, чем мой код "доказательства концепции" (POC) чуть выше, но был удивлен, обнаружив, что новый код работает значительно медленнее (в 3-4 раза медленнее в разных случаях, похожих на @JospephWood, рандомизированных пример) относительно сравниваемого "оптимизированного" варианта кода POC.

Основная причина, по-видимому, больше вызовов функции сопоставления. Код POC назывался один раз за "правдоподобный" префикс. Новый код не генерирует никаких невозможных префиксов, но для каждого префикса, который он генерирует, может потребоваться несколько вызовов match() чтобы определить, возможно, меньший набор оставшихся свободных пулов. Возможно, есть более умный способ сделать это.

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

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

Нижние строки, игнорируя код специального кода "2 входа":

• Здесь нет ничего лишнего, чтобы увеличить скорость, если у вас есть ОЗУ. Но ничто не хуже, чем для максимальной нагрузки на память.

• Ничто не сравнится с подходами, основанными на подходе, для бережливой нагрузки на память. В этой мере они находятся в совершенно другой вселенной. Они также самые медленные, хотя по крайней мере в одной и той же вселенной ;-)

Код:

def matchgen(pools, ixs):
    from collections import Counter
    from collections import defaultdict
    from itertools import islice

    elt2pools = defaultdict(list)
    allpools = []
    npools = 0
    for i, count in Counter(ixs).items():
        indices = list(range(npools, npools + count))
        plist = sorted(pools[i])
        for elt in plist:
            elt2pools[elt].extend(indices)
        for i in range(count):
            allpools.append(plist)
        npools += count
    pools = allpools
    assert npools == len(pools)

    result = [None] * npools

    # Is it possible to match result[:n] not using pool
    # bady?  If not, return None.  Else return a matching,
    # a dict whose keys are pool indices and whose values
    # are a permutation of result[:n].
    def match(n, bady):

        def extend(x, seen):
            for y in elt2pools[x]:
                if y not in seen:
                    seen.add(y)
                    if y not in y2x or extend(y2x[y], seen):
                        y2x[y] = x
                        return True
            return False

        y2x = {}
        freexs = []
        # A greedy pass first to grab easy matches.
        for x in islice(result, n):
            for y in elt2pools[x]:
                if y not in y2x and y != bady:
                    y2x[y] = x
                    break
            else:
                freexs.append(x)

        # Now do real work.
        for x in freexs:
            if not extend(x, {bady}):
                return None
        return y2x

    def inner(j, freepools): # fill result[j:]
        from bisect import bisect_left
        if j >= npools:
            yield tuple(result)
            return
        if j:
            new_freepools = set()
            allcands = set()
            exhausted = set()  # free pools with elts too small
            atleast = result[j-1]
            for pi in freepools:
                if pi not in new_freepools:
                    m = match(j, pi)
                    if not m:  # match must use pi
                        continue
                    # Since 'm' is a match to result[:j],
                    # any pool in freepools it does _not_
                    # use must still be free.
                    new_freepools |= freepools - m.keys()
                    assert pi in new_freepools
                # pi is free with respect to result[:j].
                pool = pools[pi]
                if pool[-1] < atleast:
                    exhausted.add(pi)
                else:
                    i = bisect_left(pool, atleast)
                    allcands.update(pool[i:])
            if exhausted:
                freepools -= exhausted
                new_freepools -= exhausted
        else: # j == 0
            new_freepools = freepools
            allcands = elt2pools.keys()

        for result[j] in sorted(allcands):
            yield from inner(j + 1, new_freepools)

    return inner(0, set(range(npools)))

Примечание: у этого есть свои классы "плохих дел". Например, передача 128 копий [0, 1] потребляет около 2 минут (!) Времени на моем поле, чтобы найти результаты 129. Код POC занимает менее секунды, в то время как некоторые из несогласованных подходов появляются мгновенно.

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

Прагматический гибрид

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

Очень похожие пулы заставляют множество бесплатных бассейнов медленно сокращаться (или вообще не уменьшать). Но в этом случае пулы настолько схожи, что редко имеет значение, из которого берется элемент. Таким образом, нижеприведенный подход не пытается точно отслеживать свободные пулы, выбирает произвольные пулы, пока они, очевидно, доступны, и прибегает к сопоставлению графа только тогда, когда он застревает. Кажется, это хорошо работает. В качестве крайнего примера, 129 результатов из 128 [0, 1] пулов поставляются менее чем за десятую часть секунды вместо двух минут. Оказывается, в этом случае никогда не нужно делать сопоставление графов.

Еще одна проблема с кодом POC (и, тем более, для другого подхода, основанного на совпадениях), заключалась в возможности вращения колесиков в течение длительного времени после того, как был получен последний результат. Прагматичный взлом полностью решает эту проблему ;-) Последний кортеж последовательности легко вычисляется заранее, а код вызывает внутреннее исключение, чтобы закончить все сразу после того, как был доставлен последний кортеж.

Что это для меня! Обобщение дела "два входа" оставалось бы очень интересным для меня, но теперь все чешуи, которые я получил от других подходов, были поцарапаны.

def combogen(pools, ixs):
    from collections import Counter
    from collections import defaultdict
    from itertools import islice

    elt2pools = defaultdict(set)
    npools = 0
    cands = []
    MAXTUPLE = []
    for i, count in Counter(ixs).items():
        indices = set(range(npools, npools + count))
        huge = None
        for elt in pools[i]:
            elt2pools[elt] |= indices
            for i in range(count):
                cands.append(elt)
            if huge is None or elt > huge:
                huge = elt
        MAXTUPLE.extend([huge] * count)
        npools += count
    MAXTUPLE = tuple(sorted(MAXTUPLE))
    cands.sort()
    ncands = len(cands)
    ALLPOOLS = set(range(npools))
    availpools = ALLPOOLS.copy()
    result = [None] * npools

    class Finished(Exception):
        pass

    # Is it possible to match result[:n]? If not, return None.  Else
    # return a matching, a dict whose keys are pool indices and
    # whose values are a permutation of result[:n].
    def match(n):

        def extend(x, seen):
            for y in elt2pools[x]:
                if y not in seen:
                    seen.add(y)
                    if y not in y2x or extend(y2x[y], seen):
                        y2x[y] = x
                        return True
            return False

        y2x = {}
        freexs = []
        # A greedy pass first to grab easy matches.
        for x in islice(result, n):
            for y in elt2pools[x]:
                if y not in y2x:
                    y2x[y] = x
                    break
            else:
                freexs.append(x)

        # Now do real work.
        seen = set()
        for x in freexs:
            seen.clear()
            if not extend(x, seen):
                return None
        return y2x

    def inner(i, j):  # fill result[j:] with cands[i:]
        nonlocal availpools
        if j >= npools:
            r = tuple(result)
            yield r
            if r == MAXTUPLE:
                raise Finished
            return
        restore_availpools = None
        last = None
        jp1 = j + 1
        for i in range(i, ncands):
            elt = cands[i]
            if elt == last:
                continue
            last = result[j] = elt
            pools = elt2pools[elt] & availpools
            if pools:
                pool = pools.pop() # pick one - arbitrary
                availpools.remove(pool)
            else:
                # Find _a_ matching, and if that possible fiddle
                # availpools to pretend that the one we used all
                # along.
                m = match(jp1)
                if not m: # the prefix can't be extended with elt
                    continue
                if restore_availpools is None:
                    restore_availpools = availpools.copy()
                availpools = ALLPOOLS - m.keys()
                # Find a pool from which elt was taken.
                for pool, v in m.items():
                    if v == elt:
                        break
                else:
                    assert False
            yield from inner(i+1, jp1)
            availpools.add(pool)

        if restore_availpools is not None:
            availpools = restore_availpools

    try:
        yield from inner(0, 0)
    except Finished:
        pass

Ответ 2

Это сложная проблема. Я думаю, что ваш лучший выбор в общем случае - реализовать hash table где ключ является multiset а значение - это ваша фактическая комбинация. Это похоже на то, что упоминал @ErikWolf, однако эти методы позволяют избежать дублирования в первую очередь, поэтому фильтрация не требуется. Он также возвращает правильный результат, когда мы сталкиваемся с multisets.

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

Как упоминалось в комментариях, один из подходов, который кажется жизнеспособным, состоит в том, чтобы объединить все пулы и просто создать комбинации этого объединенного пула, выберите количество пулов. Вам понадобится инструмент, способный генерировать комбинации мультимножеств, который есть тот, который я знаю о том, что доступно в python. Это в sympy библиотеке from sympy.utilities.iterables import multiset_combinations. Проблема с этим состоит в том, что мы до сих пор производят повторяющиеся значения и хуже, мы производим результаты, которые невозможно получить с аналогичным set и product комбо. Например, если бы мы сделали что-то вроде сортировки и объединили все пулы с OP и применили следующее:

list(multiset_permutations([1,2,2,3,3,4,4,5]))

Пара результатов будет [1 2 2] и [4 4 5] которые невозможно получить из [[1, 2, 3], [2, 3, 4], [3, 4, 5]],

Вне особых случаев я не вижу, как можно избежать проверки всех возможных продуктов. Надеюсь, я ошибаюсь.

Обзор алгоритма
Основная идея состоит в том, чтобы сопоставить комбинации нашего произведения векторов с уникальными комбинациями, не отфильтровывая дубликаты. Пример, заданный OP (т.е. (1, 2, 3) и (1, 3, 2)), должен отображать только одно значение (либо один из них, как порядок не имеет значения). Заметим, что два вектора являются одинаковыми множествами. Теперь у нас также есть ситуации вроде:

vec1 = (1, 2, 1)
vec2 = (2, 1, 1)
vec3 = (2, 2, 1)

Нам нужны vec1 и vec2 для сопоставления с тем же значением, тогда как vec3 необходимо сопоставить с его собственным значением. Это проблема с множествами, так как все эти эквивалентные множества (с множествами, элементы уникальны, поэтому {a, b, b} и {a, b} эквивалентны).

Именно здесь вступают в действие мультимножители. С мультимножествами (2, 2, 1) и (1, 2, 1) различны, однако (1, 2, 1) и (2, 1, 1) одинаковы. Это хорошо. Теперь у нас есть способ генерации уникальных ключей.

Поскольку я не программист на python, поэтому я C++.

У нас возникнут некоторые проблемы, если мы попытаемся реализовать все выше, чем есть. Насколько мне известно, вы не можете использовать std::multiset<int> в качестве ключевой части для std::unordered_map. Однако мы можем для обычной std::map. Это не так хорошо, как хэш-таблица внизу (это на самом деле красно-черное дерево), но она по-прежнему дает достойную производительность. Вот:

void cartestionCombos(std::vector<std::vector<int> > v, bool verbose) {

    std::map<std::multiset<int>, std::vector<int> > cartCombs;

    unsigned long int len = v.size();
    unsigned long int myProd = 1;
    std::vector<unsigned long int> s(len);

    for (std::size_t j = 0; j < len; ++j) {
        myProd *= v[j].size();
        s[j] = v[j].size() - 1;
    }

    unsigned long int loopLim = myProd - 1;
    std::vector<std::vector<int> > res(myProd, std::vector<int>());
    std::vector<unsigned long int> myCounter(len, 0);
    std::vector<int> value(len, 0);
    std::multiset<int> key;

    for (std::size_t j = 0; j < loopLim; ++j) {
        key.clear();

        for (std::size_t k = 0; k < len; ++k) {
            value[k] = v[k][myCounter[k]];
            key.insert(value[k]);
        }

        cartCombs.insert({key, value});

        int test = 0;
        while (myCounter[test] == s[test]) {
            myCounter[test] = 0;
            ++test;
        }

        ++myCounter[test];
    }

    key.clear();
    // Get last possible combination
    for (std::size_t k = 0; k < len; ++k) {
        value[k] = v[k][myCounter[k]];
        key.insert(value[k]);
    }

    cartCombs.insert({key, value});

    if (verbose) {
        int count = 1;

        for (std::pair<std::multiset<int>, std::vector<int> > element : cartCombs) {
            std::string tempStr;

            for (std::size_t k = 0; k < len; ++k)
                tempStr += std::to_string(element.second[k]) + ' ';

            std::cout << count << " : " << tempStr << std::endl;
            ++count;
        }
    }
}

В тестовых случаях из 8 векторов длиной от 4 до 8, заполненных случайными целыми числами от 1 до 15, приведенный выше алгоритм работает примерно через 5 секунд на моем компьютере. Это неплохо, учитывая, что мы рассматриваем почти 2,5 миллиона общих результатов от нашего продукта, но мы можем добиться большего. Но как?

Наилучшая производительность определяется std::unordered_map с ключом, который встроен в постоянное время. Наш ключ выше построен в логарифмическом времени (мультимножество, карта и хэш-карта сложности). Итак, вопрос в том, как мы можем преодолеть эти препятствия?

Лучшее представление

Мы знаем, что мы должны отказаться от std::multiset. Нам нужен какой-то объект, который обладает свойством коммутативного типа, а также дает уникальные результаты.

Введите основную теорему арифметики

Он утверждает, что каждое число может быть однозначно представлено (с точностью до порядка факторов) произведением чисел простых чисел. Это иногда называют простым разложением.

Итак, теперь мы можем просто действовать по-прежнему, но вместо построения мультимножества мы сопоставляем каждый индекс с простым числом и умножаем результат. Это даст нам постоянное построение времени для нашего ключа. Вот пример, показывающий силу этого метода на примерах, которые мы создали ранее (NB P ниже - список чисел простых чисел... (2, 3, 5, 7, 11, etc.):

                   Maps to                    Maps to            product
vec1 = (1, 2, 1)    -->>    P[1], P[2], P[1]   --->>   3, 5, 3    -->>    45
vec2 = (2, 1, 1)    -->>    P[2], P[1], P[1]   --->>   5, 3, 3    -->>    45
vec3 = (2, 2, 1)    -->>    P[2], P[2], P[1]   --->>   5, 5, 3    -->>    75

Это круто!! vec1 и vec2 сопоставляются с тем же номером, тогда как vec3 сопоставляется с другим значением, как мы хотели.

void cartestionCombosPrimes(std::vector<std::vector<int> > v, 
                        std::vector<int> primes,
                        bool verbose) {

    std::unordered_map<int64_t, std::vector<int> > cartCombs;

    unsigned long int len = v.size();
    unsigned long int myProd = 1;
    std::vector<unsigned long int> s(len);

    for (std::size_t j = 0; j < len; ++j) {
        myProd *= v[j].size();
        s[j] = v[j].size() - 1;
    }

    unsigned long int loopLim = myProd - 1;
    std::vector<std::vector<int> > res(myProd, std::vector<int>());
    std::vector<unsigned long int> myCounter(len, 0);
    std::vector<int> value(len, 0);
    int64_t key;

    for (std::size_t j = 0; j < loopLim; ++j) {
        key = 1;

        for (std::size_t k = 0; k < len; ++k) {
            value[k] = v[k][myCounter[k]];
            key *= primes[value[k]];
        }

        cartCombs.insert({key, value});

        int test = 0;
        while (myCounter[test] == s[test]) {
            myCounter[test] = 0;
            ++test;
        }

        ++myCounter[test];
    }

    key = 1;
    // Get last possible combination
    for (std::size_t k = 0; k < len; ++k) {
        value[k] = v[k][myCounter[k]];
        key *= primes[value[k]];
    }

    cartCombs.insert({key, value});
    std::cout << cartCombs.size() << std::endl;

    if (verbose) {
        int count = 1;

        for (std::pair<int, std::vector<int> > element : cartCombs) {
            std::string tempStr;

            for (std::size_t k = 0; k < len; ++k)
                tempStr += std::to_string(element.second[k]) + ' ';

            std::cout << count << " : " << tempStr << std::endl;
            ++count;
        }
    }
}

В том же примере выше, который генерирует почти 2,5 миллиона продуктов, приведенный выше алгоритм возвращает тот же результат менее чем за 0,3 секунды.

Есть пара предостережений с этим последним методом. Нам нужно, чтобы наши простые числа генерировались априори, и если у нас много векторов в нашем декартовом произведении, ключ мог бы выйти за пределы int64_t. Первый вопрос не должен быть таким трудным для преодоления, поскольку для генерации простых чисел имеется много ресурсов (библиотеки, таблицы поиска и т.д.). Я не уверен, но я читал, что последняя проблема не должна быть проблемой для python поскольку целые числа имеют произвольную точность (целые числа Python).

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

vec1 = (12345.65, 5, 5432.11111)
vec2 = (2222.22, 0.000005, 5)
vec3 = (5, 0.5, 0.8)

Оценив их, мы получим:

rank1 = (6, 3, 5)
rank2 = (4, 0, 3)
rank3 = (3, 1, 2)

И теперь они могут использоваться вместо фактических значений для создания вашего ключа. Единственной частью кода, который будет изменяться, будет цикл for, который создает ключ (и, конечно, объект rank, который нужно будет создать):

for (std::size_t k = 0; k < len; ++k) {
    value[k] = v[k][myCounter[k]];
    key *= primes[rank[k][myCounter[k]]];
}

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

Кроме того, если кому-то интересно, вот пример, который я использовал выше:

[1 10 14  6],
[7  2  4  8  3 11 12],
[11  3 13  4 15  8  6  5],
[10  1  3  2  9  5  7],
[1  5 10  3  8 14],
[15  3  7 10  4  5  8  6],
[14  9 11 15],
[7  6 13 14 10 11  9  4]

Он должен вернуть 162295 уникальных комбинаций.

Ответ 3

Одним из способов сохранения некоторой работы может быть создание дедуплицированных комбинаций из первых k выбранных пулов, а затем их расширение для дедуплицированных комбинаций первого k + 1. Это позволяет избежать индивидуальной генерации и отказа от всех комбинаций длиной-20, которые выбрали 2, 1 вместо 1, 2 из первых двух пулов:

def combinations_from_pools(pools):
    # 1-element set whose one element is an empty tuple.
    # With no built-in hashable multiset type, sorted tuples are probably the most efficient
    # multiset representation.
    combos = {()}
    for pool in pools:
        combos = {tuple(sorted(combo + (elem,))) for combo in combos for elem in pool}
    return combos

Однако, учитывая размеры ввода, о которых вы говорите, независимо от того, насколько эффективно вы генерируете комбинации, вы никогда не сможете обработать их все. Даже с 20 одинаковыми 1000-элементными пулами было бы 496432432489450355564471512635900731810050 комбинаций (1019 выберите 20 по формуле звезд и баров) или около 5e41. Если бы вы захватили Землю и посвятили всю вычислительную мощность всего человечества всему человечеству этой задаче, вы все равно не могли бы впасть в это. Вам нужно найти лучший способ решить вашу основную задачу.

Ответ 4

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

Идея такова.

Итак, у нас есть N пулов {P ₁ ,..., P _N }, из которых мы должны извлечь наши комбинации. Мы можем легко определить наименьшую комбинацию (относительно упомянутого лексикографического упорядочения). Пусть это (x ₁, x ₂..., x _N-1, x _N) (где x ₁ <= x ₂ <=... <= x _N-1 <= x _N, и каждый x _j равен просто самый маленький элемент из одного из пулов {P _i }). За этой наименьшей комбинацией последуют ноль или более комбинаций, где префикс x ₁, x ₂..., x _N-1 является таким же, а последнее положение выполняется по возрастающей последовательности значений. Как мы можем идентифицировать эту последовательность?

Введем следующее определение:

Учитывая префикс комбинации C = (x ₁, x ₂..., x _K-1, x _K) (где K <N), пул P _i называется свободным относительно C, если последний (префикс) может вытягиваться из остальных бассейнов.

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

Итак, для префикса (x ₁, x ₂..., x _N-1) нашей первой комбинации мы можем идентифицировать все свободные пулы {FP _i }. Любой из них может быть использован для выбора элемента для последней позиции. Поэтому представляющая интерес последовательность представляет собой отсортированный набор элементов из {FP ₁ U FP ₂ U...}, которые больше или равны x _N-1.

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

Таким образом, следующий рекурсивный алгоритм должен выполнять работу:

1. Начните с пустого префикса комбинации C. В этот момент все пулы свободны.
2. Если длина C равна N, то выведите C и верните.
3. Объедините свободные пулы в один отсортированный список S и удалите из него все элементы, которые меньше, чем последний элемент C.
4. Для каждого значения x из S do
5. • Новый префикс комбинации - C '= (C, x)
6. • Если текущий префикс комбинации вырос на один, некоторые из бесплатных пулов перестают быть свободными. Определите их и перепишите на шаг 1 с обновленным списком свободных пулов и префиксом комбинации C '.

Ответ 5

Вы можете реализовать список хешируемых и использовать python set() для фильтрации всех дубликатов. Ваша хэш-функция просто должна игнорировать порядок в списке, который может быть достигнут с помощью коллекций.

from collections import Counter

class HashableList(list):
    def __hash__(self):
        return hash(frozenset(Counter(self)))
    def __eq__(self, other):
        return hash(self) == hash(other)

x = HashableList([1,2,3])
y = HashableList([3,2,1])

print set([x,y])

Это возвращает:

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

Ответ 6

Вот что я придумал:

class Combination:
    def __init__(self, combination):
        self.combination = tuple(sorted(combination))

    def __eq__(self, other):
        return self.combination == self.combination

    def __hash__(self):
        return self.combination.__hash__()

    def __repr__(self):
        return self.combination.__repr__()

    def __getitem__(self, i):
        return self.combination[i]

Затем,

pools = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
part = (0, 0, 1)
set(Combination(combin) for combin in product(*(pools[i] for i in part)))

Выходы:

{(1, 1, 2),
 (1, 1, 3),
 (1, 1, 4),
 (1, 2, 2),
 (1, 2, 3),
 (1, 2, 4),
 (1, 3, 3),
 (1, 3, 4),
 (2, 2, 2),
 (2, 2, 3),
 (2, 2, 4),
 (2, 3, 3),
 (2, 3, 4),
 (3, 3, 3),
 (3, 3, 4)}

Не уверен, действительно ли это то, что вы ищете.