[ Python ] itertools.combinations(iterable, r)

오늘 이 함수를 보게된 발단은 프로그래머스 코딩테스트 정답 제출 후, 다른 사람의 풀이에서 이 함수를 사용하여 엄청나게 짧은 코드로 정답을 제출한 사람을 발견한 것이었다.

오늘 풀었던 문제는 Lv1. 삼총사 문제.

내가 제출한 코드는

def solution(number):
    answer = 0
    for i in range(len(number)-2) :
        for j in range(i + 1, len(number) - 1) :
            for k in range(j + 1, len(number)) :
                if number[i] + number[j] + number[k] == 0 :
                    answer += 1
    return answer

다른 사람이 제출한 코드는

def solution (number) :
    from itertools import combinations
    cnt = 0
    for i in combinations(number,3) :
        if sum(i) == 0 :
            cnt += 1
    return cnt

itertools 패키지에서 combination모듈을 import하여 엄청나게 간단하게 문제를 풀어버렸다!!

그래서 이 itertools와 combinations가 뭔지 알아보기로 했다.

 

---

itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.8.14 문서

위 링크는 아래 함수의 내용이 포함되어 itertools에 대한 설명히 자세히 되어있는 docs 페이지

 

itertools.combinations(iterable, r)

- 효율적인 루핑을 위한 이터레이터를 만드는 함수

 

자체적으로 혹은 조합하여 유용한 빠르고 메모리 효율적인 도구의 핵심 집합을 표준화합니다.

간결하고 효율적인 특수화된 도구를 구성할 수 있도록 하는 '이터레이터 대수(iterator algebra)'를 형성합니다.

 

 

이터레이터 도구 함수

다음 모듈 함수는 모두 이터레이터를 생성하고 반환합니다.

일부는 길이가 무한한 스트림을 제공해서 스트림을 자르는 함수나 루프로만 액세스해야 합니다.

 

itertools.combinations(iterable, r)

 

입력 iterable에서 요소의 길이 r 서브 시퀀스들을 반환합니다.

 

조합(combination) 튜플은 입력 iterable의 순서에 따라 사전식 순서로 방출됩니다.

따라서, 입력 iterable이 정렬되어 있으면, 조합 튜플이 정렬된 순서로 생성됩니다.

 

요소는 값이 아니라 위치로 고유성을 다룹니다.

따라서, 입력 요소가 고유하면, 각 조합에 반복 값이 없습니다.

def combinations(iterbale, r)
	# combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    
    # combinations('ABCD', 2) --> AB AC AD BC BD CD 이 예로 함수가 어떻게 실행되는지 살펴보자!
   	pool = tuple(iterable)  # pool =('A', 'B', 'C', 'D')
    n = len(pool)  # n = 4
    
    if r > n :  # 2 < 4이므로 False
    	return
    indices = list(range(r))  # indices = [0, 1]
    yield tuple(pool[i] for i in indices)  # ('A','B')
    while True :
    	for i in reversed(range(r)) :  # i=1, i=0
        	if indices[i] != i + n - r  # i=1, 1 != 1 + 4 - 2 = 3 break/ i=0, 0 != 0 + 4 - 2 break
            	break
        else :
            return
        indices[i] += 1  # [0, 2]/ [0, 3]/ [1, 3]/ [2, 3]
        # print(indices)
        for j in range(i+1, r) :  
        	indices[j] = indices[j-1] + 1
          yield tuple(pool[i] for i in indices)  # ('A', 'C')/ ('A', 'D')/ ('B', 'C')/ ('B', 'D')/ ('C', 'D')

사실 while문 안의 for문이 지나고 else문에서 들여쓰기가 잘못된 것이 아닌가?하는 생각이 들었는데

위에 코드가 맞는것이었다.

위에 if문이랑은 들여쓰기가 다른데 else문부터 코드가 어떻게 흘러가는지 모르겠다.

(아래 링크는 위 코드에서 yield 개념도 확실히 잘 모르겠고 위 함수를 출력해 볼 때 참고한 개념)

파이썬 코딩 도장: 40.1 제너레이터와 yield 알아보기

 

combinations()의 코드는 요소가 정렬된 순서(입력 풀에서의 위치에 따라)가 아닌 항목을 걸러내어 만들어지는

permutations()의 서브 시퀀스로 표현될 수도 있습니다.

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

반환되는 항목 수는 0 <= r <= n 일 때는 n! / r! / (n-r)! 이고 r > n일 때는 0입니다.