반복하지 않고 모든 조합을 얻는 방법은 무엇입니까?

Question

그래서,이 배열 진형 :

array = ['A', 'B', 'C', 'D', 'E', 'F']

그리고, 각각의 고유, 반복되지 않는 조합을 인쇄과 같이 할 수 파이썬을 얻기 전에 잠시 동안 놀았 :

AB, 
AC, 
AD, 
AE, 
AF, 
BC, 
BD, 
BE, 
BF, 
CD, 
CE, 
CF, 
DE, 
DF, 
EF, 

그러나 지금, 나는 새로운 배열로이 모든 것을 가지고 싶습니다

array2 = ['AB', 'AC', 'AD'...., 'EF']

반복이없는 재 배열을 제외한 3 요소 길이의 모든 조합을 인쇄하십시오.

내가 '반복없이'가 무엇을 의미 : 반복없이와 3 요소 긴 조합

AB, CD 및 EF이지만, AB, BD 및 EF는 반복과 3 요소 길이의 조합입니다, 'B'이 'AB'와 'BD''모두에 나타납니다.

내가 '를 포함하지 않는 재 배열'을 의미하는 것 :

는

AB는, CD는, EF는 2 글자의 모든 요소가 같은 (BA 때문에 AB 재 배열, BA, DC, FE와 같은 것 , DC는 CD 재배치되며 FE는 EF 재정렬됩니다. 그래서 이상적으로는 다음과 같이 인쇄 할 것입니다 :

AB CD EF, 
AB CE DF, 
AB CF DE, 
AC BD EF, 
AC BE DF, 
AC BF DE, 
AD BC EF, 
AD BE CF, 
AD BF CE, 
AE BC DF, 
AE BD CF, 
AE BF CD, 
AF BC DE, 
AF BD CE, 
AF BE CD, 

나는 2 문자 요소가 반복되지 않는 모든 조합이라고 생각합니다.

어떻게 인쇄하나요? 감사! (모든 itertools없이)

Answer 1

Generator 계 순환 방식 :

가

def comb(s): 
    if len(s) == 2: 
    yield [s] 
    for x in s[1:]: 
    first = ''.join((s[0], x)) 
    rest = ''.join(c for c in s if c not in first) 
    for com in comb(rest): 
     yield [first] + com 

>>> list(comb('ABCDEF')) 
[['AB', 'CD', 'EF'], 
['AB', 'CE', 'DF'], 
['AB', 'CF', 'DE'], 
['AC', 'BD', 'EF'], 
['AC', 'BE', 'DF'], 
['AC', 'BF', 'DE'], 
['AD', 'BC', 'EF'], 
['AD', 'BE', 'CF'], 
['AD', 'BF', 'CE'], 
['AE', 'BC', 'DF'], 
['AE', 'BD', 'CF'], 
['AE', 'BF', 'CD'], 
['AF', 'BC', 'DE'], 
['AF', 'BD', 'CE'], 
['AF', 'BE', 'CD']] 

이 다른 원소의 각각과 쌍을 첫 번째 요소를 취하고, 만들어 질 수있는 모든 철저한 쌍리스트와 생성 된 쌍을 겸비한 나머지 요소들로부터. 기본 경우는 요소가 두 개인 경우입니다.

참고 :rest 조립은 초기 문자열/시퀀스에 반복이 없음을 전제로합니다.

Answer 2

다음은 itertools을 사용하는 무차별 대입 재귀 적 버전입니다. 쌍을 생성 한 다음 해당 쌍의 모든 조합을 만들고 집합을 사용하여 문자를 반복하는 조합을 제거합니다. 그것은 입니다.은 schwobaseggl의 생성기보다 효율적이지 않지만, combinations이 매우 빠르기 때문에 작은 문자열에서는 여전히 빠릅니다. 내 2GHz의 컴퓨터에

from itertools import combinations 

def pairs(s): 
    n = len(s) 
    numgroups = n // 2 
    for v in combinations(map(''.join, combinations(s, 2)), numgroups): 
     if len(set(i for u in v for i in u)) == n: 
      yield v 

for t in pairs('ABCDEF'): 
    print(t) 

출력

('AB', 'CD', 'EF') 
('AB', 'CE', 'DF') 
('AB', 'CF', 'DE') 
('AC', 'BD', 'EF') 
('AC', 'BE', 'DF') 
('AC', 'BF', 'DE') 
('AD', 'BC', 'EF') 
('AD', 'BE', 'CF') 
('AD', 'BF', 'CE') 
('AE', 'BC', 'DF') 
('AE', 'BD', 'CF') 
('AE', 'BF', 'CD') 
('AF', 'BC', 'DE') 
('AF', 'BD', 'CE') 
('AF', 'BE', 'CD') 

그것은 pairs('ABCDEFGHIJ')의 945 개 결과를 인쇄하는 13 개의 초 정도 걸립니다. 이에 비해 schwobaseggl의 comb은 0.193 초 밖에 걸리지 않습니다.:)

---

다음은 더 똑똑한 itertools 버전입니다. 이것은 여전히 ​​필요한 것보다 더 많은 일을하지만, schwobaseggl의 comb 생성기보다 약 2 배 정도 느립니다. 먼저 원래 문자열의 절반 크기의 조합을 만들고 set.difference을 사용하여 보완 조합을 만듭니다. 그런 다음 해당 조합을 원래 조합과 조합하도록 순서를 바꿉니다.

from itertools import combinations, permutations 

def pairs(s): 
    a = set(s) 
    for u in combinations(s, len(s) // 2): 
     b = tuple(sorted(a.difference(u))) 
     if b < u: 
      break 
     for v in permutations(b): 
      c = [*zip(u, v)] 
      if all(i<j for i, j in c): 
       yield [*map(''.join, c)] 

Answer 3

오후 2Ring의 코드에 빠른 변화 :

from itertools import combinations 
array = ['A', 'B', 'C', 'D', 'E', 'F'] 
n = len(array) 
numgroups = n // 2 

array2 = map(''.join, combinations(array,2)) 
result = (' '.join(com) for com in combinations(array2,numgroups) if len(set(''.join(com)))==n) 
for res in result: 
    print res