[TIL] itertools. permutations, combinations 순열과 조합

AI 웹개발반

[TIL] itertools. permutations, combinations 순열과 조합

째깍단 2023. 5. 3. 22:15

알고리즘 문제에서 자주쓰이는

itertools의 combinations, permutations 를 알아보자

permutations(iterable한 객체, r = 조합할 요소 개수 or None)

순열 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것

인자 : iterable객체, ( r은 선택 사항) 한 개를 받고 옵션으로 개수!

r이 지정되지 않았거나 None인 경우 r 의 기본값은 iterable객체 길이를 받는다.

튜플로 생성되며 요소의 순서에 따라 정렬되어 나열된다.

- 예시

permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC

permutations(range(3)) --> 012 021 102 120 201 210

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

combinations(iterable한 객체, r = 조합할 요소 개수)

조합 : 원소에서 주어진 수만큼의 원소들을 고르는 방법으로 요소의 순서는 중요하지 않다.

인자 : iterable객체 , r 두 개를 받는다

튜플로 출력, 입력 요소가 고유하면 반복되는 값이 없다.

- 예시

combinations('ABCD', 2) --> AB AC AD BC BD CD

combinations(range(4), 3) --> 012 013 023 123

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

combinations, permutations모두 재귀함수로 구현하면 보다 간결한 코드로 구현이 가능한 듯하다!

+ 예시 and product, combination_with_replacement

예	결과
product('ABCD', repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD