Я знаю с помощью itertools
мы можем генерировать products
, permutations
а также combinations
, Тем не менее, рассматривая случай, как:
max_allowed_len(sequence)= 3
iterable= ABC
repeat= 3 (or just `range(len('ABC')`)
Я заинтересован в создании всех различных повторяемых наборов ABC с len(sequence)=0 len(sequence)=1 OR len(sequence)=2 and len(sequence)=3
имея повторения р. Это своего рода странная перестановка с повторениями, допускающими разные последовательности. Итак, мое пространство:
3^0 + 3^1 + 3^2 + 3^3= 1 + 3 + 9+ 27= 40
Может кто-нибудь предложить мне, как реализовать это в Python или даже C / C ++?
`’0′ (ничего (длина последовательности 0))
Последовательность с длиной = 1
'A'
'B'
'C'
Последовательность с длиной = 2
'AA'
'BB'
'CC'
'AB'
'AC',...
Последовательность с длиной = 3
'AAB'
'ABA'
'AAC'
'ACA'`
и это продолжается. Так что здесь у меня были длины 0, 1, 2 и 3 (макс).
Вот (относительно) простой способ создать такой итератор для ввода строки. Выводит пустую строку ''
для нулевой последовательности. Я называю это дважды, чтобы сделать вывод легче для чтения.
Ядром функции является цикл выражения генератора, использующий product
с repeat
arg для генерации итераторов для каждой группы продуктов длины от нуля до длины входной строки. Эти итераторы затем потребляются chain.from_iterable
и кормили ''.join
метод, используя imap
на самом деле вызвать метод для каждого кортежа, который был произведен product
,
from itertools import product, chain, imap
def all_prod(s):
return imap(''.join, chain.from_iterable(product(s, repeat=i) for i in range(len(s)+1)))
print(list(all_prod('ABC')))
for s in all_prod('abc'):
print(s)
выход
['', 'A', 'B', 'C', 'AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC', 'AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ABC', 'ACA', 'ACB', 'ACC', 'BAA', 'BAB', 'BAC', 'BBA', 'BBB', 'BBC', 'BCA', 'BCB', 'BCC', 'CAA', 'CAB', 'CAC', 'CBA', 'CBB', 'CBC', 'CCA', 'CCB', 'CCC']
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc
FWIW, вот альтернативная версия, которая использует простой chain
функция; он использует дополнительный цикл вместо imap
, так что это может быть менее эффективно, но я полагаю, что это также может быть немного проще для понимания.
def all_prod(s):
return (''.join(v) for u in chain(product(s, repeat=i) for i in range(len(s)+1)) for v in u)
Других решений пока нет …