여러개의 (가능한 반복되는) 글자를 사용하여 모든 고유 단어를 효율적으로 생성하는 방법

Question

글자 수가 3 개와 2 개라고하고 가능한 모든 단어를 찾고 싶습니다. itertools.permutations과 itertools.product을 시도했지만 도움이되지 않았습니다.

결과는 permutations에 반복됩니다 (즉, 동일한 단어가 여러 번 나타남). 예를 들어 '

> print [''.join(i) for i in itertools.product('ab', repeat=3)] 
['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb'] 

이 개 A의 나는`['AAB '를 얻으려면 하나의 b :

> print [''.join(i) for i in itertools.permutations('aab', 3)] 
['aab', 'aba', 'aab', 'aba', 'baa', 'baa'] 

2) product의 결과는 문자 하나에 단어를 포함 할 수 있습니다 aba ','baa ']. 또한 결과가 매우 커질 수 있기 때문에 이터레이터를 사용하고 목록을 사용하지 않는 방법 (또는 메모리에 모든 것을 저장하는 다른 방법)이 필요합니다.

Answer 1

이 문제가 마음에 듭니다.

1. 문자 목록을 복제되지 않은 문자로 분할합니다.
2. itertools을 사용하여 중복되지 않은 문자의 고유 순열을 한 번에 하나씩 생성 할 수 있습니다.
3. 복제 된 각 문자에 대해 한 번에 하나씩 문자를 삽입하는 방법을 생성 할 수 있습니다. (이것은 우리가 별개의 이러한 중복의 서로 다른 주문을 취급하지 않도록 별도로 수행해야합니다.)

Answer 2

def _permute(xs): 
    if not xs: 
     yield() 
    for x in xs: 
     xs[x] -= 1 
     if not xs[x]: 
      xs.pop(x) 
     for ys in _permute(xs): 
      yield (x,) + ys 
     xs[x] += 1 

from collections import Counter 
def permute(xs): 
    return _permute(Counter(xs)) 

사용법 : 나는이를 저장하지 않으 말했듯이

>>> list(permute('aab')) 
[('a', 'a', 'b'), ('a', 'b', 'a'), ('b', 'a', 'a')] 
>>> [''.join(xs) for xs in permute('aab')] 
['aab', 'aba', 'baa'] 
>>> map(''.join, permute('aab')) # list(map(...)) in Python 3.x 
['aab', 'aba', 'baa']