순열과 조합 - combinations, permutations

조합

조합이란 n개의 원소를 사용해서 순서의 관계없이 r개의 배열로 나타내는 것을 말한다.

조합은 순서가 없어 원소의 종류가 같으면 다같은 배열로 나타낸다.

combinations

python combinations 공식문서

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    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)

순열

순열은 n개의 원소를 이용해서 순서를 정해 r개의 배열로 나타내는 것을 말한다.

순열은 순서가 있기 때문에 원소의 종류가 같아도 순서가 다르면 다른 배열이 된다.

permutations

permutations 공식문서
보통은 for문을 이용하여 permutations을 구현합니다.

파이썬에서는

itertools.permutation를 이용하면, for문을 사용하지 않고도 순열을 구할 수 있습니다.

import itertools

pool = ['A', 'B', 'C']
print(list(map(''.join, itertools.permutations(pool)))) # 3개의 원소로 수열 만들기
print(list(map(''.join, itertools.permutations(pool, 2)))) # 2개의 원소로 수열 만들기