Перестановки списка с дубликатами - PullRequest
Новая
       48

Перестановки списка с дубликатами

3 голосов
/ 20 октября 2019

Я пытаюсь создать генератор целочисленных разделов, в котором порядок имеет значение , а все части меньше k (например, если k = 10 и n = 100, [5, 95] не будет действительным, поскольку 95> = 10). Я уже скопировал генератор (и изменил его), где порядок не имеет значения с этого веб-сайта , и сейчас пытаюсь создать генератор, который проходит через перестановки каждого раздела.

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

set(itertools.permutations(partition))

Это очень неэффективно. Когда partition имеет что-то с дубликатами, он повторяет все дубликаты. Например, когда partition = [1, 1, 1, 1, 1, 1, 1], itertools будет проходить через все 7! = 5040 разделов, когда существует только одна уникальная перестановка.

Как я могу сделать это более эффективным? Я буду рассматривать значения n порядка 10 ^ 10 и выше, поэтому эффективность очень важна.

Если это полезно, обратите внимание, что все части раздела меньше k.

Редактировать: Я думаю, что я (в основном) получил его. Однако есть ошибка. 

def helper(current, index, available, freqList):
    if index >= len(freqList) or available == []:
        yield current
        return
    else:
        if freqList[index] != 0:
            for combo in itertools.combinations(available, freqList[index]):
                yield helper(new(current, index, combo), index + 1, delete(available, combo), freqList)
        else:
            yield helper(current, index + 1, available, freqList)
def permutations(partition, k):
    #returns permutations of partition

    length = len(partition)
    freqList = [partition.count(i) for i in range(k)]

    available = [i for i in range(length)]
    return helper([0]*length, 1, available, freqList)

delete(L, T) возвращает копию L без элементов в T. new(L, i, T) возвращает копию L, но со всеми индексами в T, замененными на i.

То, что это делает, - это, в основном, итерация комбинаций того, куда может идти каждое числоДопустим, в разделе 10 1, 5 2 и 7 3. Он перебирает возможные пробелы, которые могут пройти 1 с. Затем он перебирает все пробелы, которые могут пройти 2, учитывая, что 1 занимают другие пространства. Наконец, он перебирает все пробелы, которые могут пройти 3s, если 1 и 2 занимают их места.

В этом коде есть ошибка. По какой-то причине permutations возвращает генератор генераторов генераторов ... списков, вложенных m раз, где m - это максимальное количество элементов в partition. Например, если partition = [1, 1, 1, 3, 3, 3], мне нужно будет сделать 

for gen1 in permutations(partition, k):
    for gen2 in gen1:
        for gen3 in gen2:
            for partition in gen3:
                #something else

, чтобы получить доступ к разделам.

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

Редактировать 2: Дэвис Херринг упомянул в комментариях, что я мог бы просто сделать yield from (helper(...), чтобы решить проблему. Я не знал, что смогу это сделать, и это сработало. Теперь меня интересуют другие решения или оптимизации для этого.

...