Максимально возможная генерация перестановки с определенными значениями элементов в Python

Question

Попытка генерировать перестановки, может использоваться с генератором или сгенерированным списком списков (но, может быть, мне нужно много памяти?) Посмотрел в Интернете и SO, но не смог найти версию, где я определяю значения для каждогоelement.

Кстати, сколько будет перестановок?

8 элементов с каждым значением от 1-15

Вот мой код, но, возможно, есть лучше, быстрееспособ создать его:

Любые советы приветствуются!

import time
from tqdm import tqdm
def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

plist = []

for item in tqdm(permutations('123456789ABCDEF',8)):
  plist.append(item)


len(plist)

Answer 1

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

Используйте itertools.permutations() сам. Модуль itertools уже разработан для максимальной эффективности. Модуль написан на C и всегда будет лучше, чем просто реализация на Python. Руки вниз.

Вы также тратите впустую итерации на добавлении значений в список; каждое выражение .append() требует поиска атрибута и вызова метода. Вы можете создать plist в одном выражении, вызвав list():

plist = list(permutations('123456789ABCDEF', 8))

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

Число k -перестановок n рассчитывается с помощью k! / (n - k)!) , при n = 15 и k = 8, это 15! / (15 - 8) !, так что чуть более четверти миллиарда результатов, 259_459_200 . В 64-разрядной ОС, для которой потребуется около 30 ГБ памяти (2 ГБ для объекта списка, 27 ГБ для кортежей, простые байты для 15 однозначных строк при их совместном использовании).

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

Кроме того, всегда ищите другие способы решения вашей проблемы. Генерация всех возможных перестановок создаст очень большое количество возможностей. На ваш предыдущий вопрос был получен ответ, в котором указывалось, что для , чем для конкретной задачи , поиск по 200 КБ данных для возможных кандидатов был более эффективен, чем поиск по 40 КБ для каждой возможной 8-перестановок из 8. С 259 млн. Перестановок Существует еще большая вероятность того, что обработка вашей проблемы в другом направлении может помочь в решении проблемного пространства.