순열과 조합 - combinations, permutations

이번 강의에서는 iterable의 원소로 순열과 조합을 구하는 방법을 배워봅시다.

예시)

  • 1,2,3의 숫자가 적힌 카드가 있을 때, 이 중 두 장을 꺼내는 경우의 수 -> 12, 13, 21, 23, 31, 32
  • 'A', 'B', 'C'로 만들 수 있는 경우의 수 -> 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'

다른 언어에서는..(또는 이 기능을 모르시는 분은)

보통 사람들은 for 문을 이용해 permutation 함수를 구현합니다.

import copy


def permute(l):
    n = len(l)
    result = []
    c = n * [0]

    result.append(l)

    i = 0;
    while i < n:
        if c[i] < i:
            if i % 2 == 0:
                tmp = l[0]
                l[0] = l[i]
                l[i] = tmp

            else:

                tmp = l[c[i]]
                l[c[i]] = l[i]
                l[i] = tmp

            result.append(copy.copy(l))
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1

    return result

l = [1, 2, 3, 4, 5]
print(permute(l))

출처

파이썬에서는

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개의 원소로 수열 만들기

※ 조합은 itertools.combinations를 사용해서 구할 수 있습니다. 사용법은 permutations와 비슷해요!

본 강의는 [Mark Ha]의 아이디어로 제작되었습니다.