большой набор данных с различными перестановками в Python

Question

У меня есть комбинация из 50 букв, и мне нужны отдельные перестановки всех из них, напечатанные в CSV-файл. Прямо сейчас я использовал метод more_itertools Different_permutations для создания списка. В пределах 50 букв 40 из них одинаковы, а остальные 10 букв одинаковы. Я использовал Mathematica для проверки возможных комбинаций (50! / (40! * 10!)), И их было более 10 миллиардов, так что мне интересно, является ли «Different_permutation» наиболее эффективным способом сделать это? Потому что я запускал этот код с самого утра, и он все еще работает. Спасибо.

Answer 1

Знаете ли вы, что данные будут занимать около терабайта на вашем жестком диске? ;)
(и запись займет около 6 часов для обычных HD)

Эта проблема эквивалентна генерации комбинаций. Вы можете попробовать itertools combinations метод. Если он тоже медленный, рассмотрите возможность использования битовой арифметики.

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

Краткий пример:

def nextperm(v):
    t = (v | (v - 1)) + 1
    w = t | ((((t & -t) // (v & -v)) >> 1) - 1)
    return w

v = 0b0011
print("{0:b}".format(v))
while (v != 0b1100):
    v = nextperm(v)
    print("{0:b}".format(v))

дает вывод

11   
101
110
1001
1010
1100

, что соответствует

AABB
ABAB    
ABBA
BAAB
BABA
BBAA

В моем эксперименте генерация 10 ^ 8 шагов (1/100 от вашего полного диапазона) для исходного паттерна v = 0b00000000000000000000000000000000000000001111111111 без вывода заняла 60 секунд

Редактировать: еще один эксперимент с частичным реальным выходом . Я уверен, что построение строки может быть выполнено быстрее, но я не знаю лучшего способа в Python. Моя реализация генерирует файл размером 50 МБ за 13 секунд (1/10000 реального размера), поэтому полная генерация займет 1,5 дня. Хорошая реализация построения строк (и использование более быстрого языка вместо Python) может дать выигрыш до 10 раз.

def nextperm(v):
    t = (v | (v - 1)) + 1
    w = t | ((((t & -t) // (v & -v)) >> 1) - 1)
    return w

def writeout(v):
    outs = ""
    t = v
    for i in range(50):
       outs = alphabet[(t & 1)] + outs
       t = t >> 1
    my_file.write(outs + "\n")

v = 0b00000000000000000000000000000000000000001111111111
alphabet = "AB"
my_file = open("out.txt", "w")
for i in range(1000000):
#while (v != 0b11111111110000000000000000000000000000000000000000):
    writeout(v)
    v = nextperm(v)
writeout(v)
my_file.close()

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