Перестановки неограниченной длины на python

Question

Я хочу получить итератор на все возможные строки, представляющие собой перестановки из символов имеющегося алфавита. К примеру, при алфавите ('0', '1') и длине строки 3 я хочу получить:

"000", "001", "010", ... "110", "111"

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

alphabet = {'a', 'b', 'c', 'd'}
for a in alphabet:
  for b in alphabet:
    # Смысл дальше, думаю, понятен

Ни в документации, ни на форумах я, к сожалению, не нашёл решения подобной проблемы. Но мне просто интересно: 1) верно ли, что itertools не предоставляет такой функционал? Но если да, то 2) можно ли обойтись без "наивного" кода сверху?

Answer 1

во первых есть стандартная библиотека itertools и функция product:

import itertools

print(*itertools.product((0, 1), repeat=3))

во вторых данную задачу можно свести к перебору чисел от 0 до N^M - 1, где M - кол-во цифр, N - система счисления

например в вашем примере имеется 2-ричная система со словарем (0, 1), а всего соответственно может быть 2^3 вариантов и значит надо перебрать все числа до 8 и каждое перевести из 10 ричной в 2ричную систему:

dictionary = ('0', '1')
size = 3
for i in range(len(dictionary)**size):
    value = i
    res = []
    for j in range(size):
        digit = value % len(dictionary)
        value = (value - digit) // len(dictionary)
        res.append(dictionary[digit])

    print(res[::-1])

БЛОГ НА HUSL

Перестановки неограниченной длины на python

Ответы (1 шт):