[Python3] 순열과 조합, 중복순열과 중복 조합

순열(Permutations)

예시

중괄호를 친 것은 전단계를 의미한다.

어떤 리스트에서 2개의 원소를 뽑아 나열하는 것은

1과 [2, 3, 4, 5] 중 하나를 뽑아서 배치하는 것

2와 [1, 3, 4, 5] 중 하나를 뽑아서 배치하는 것

과 같으며

만약 3개의 원소를 뽑아 나열한다고 생각하면

1개를 뽑고 나머지 2개의 원소는 2단계의 방법을 똑같이 적용하는 것이라고 생각하면 된다.

구현

이를 파이썬으로 구현하기 위해서 Generator를 사용했다.

39. Generator(제네레이터) - 파이썬 - 기본을 갈고 닦자! (wikidocs.net)

39. Generator(제네레이터)

import copy

def permu(arr, n):
    for i in range(len(arr)):
        if n == 1:
            yield [arr[i]]
        else:
            ar2 = copy.deepcopy(arr)
            ar2.remove(arr[i])
            for j in permu(ar2, n-1):
                yield [arr[i]] + j

p = permu([1, 2, 3, 4, 5], 3)
for i in p:
    print(i)

이미 선별한 원소를 제외한 리스트를 제공해야 하므로 deepcopy를 통해 새로운 배열을 할당해준다.

결과

조합

예시

순열과 마찬가지의 논리를 사용한다. 다만 구현하기가 더 쉽다.

구현

def combi(arr, n):
    for i in range(len(arr)):
        if n == 1:
            yield [arr[i]]
        else:
            for j in combi(arr[i+1:], n-1):
                yield [arr[i]] + j

p = combi([1, 2, 3, 4, 5], 3)
for i in p:
    print(i)

결과

중복 순열과 중복 조합

값을 중복해서 빼올 수 있는 경우, 구현이 오히려 간단하다.

중복 순열

import copy

def permu(arr, n):
    for i in range(len(arr)):
        if n == 1:
            yield [arr[i]]
        else:
            for j in permu(arr, n-1):
                yield [arr[i]] + j

p = permu([1, 2, 3, 4, 5], 3)
for i in p:
    print(i)

결과

중복 조합

def combi(arr, n):
    for i in range(len(arr)):
        if n == 1:
            yield [arr[i]]
        else:
            for j in combi(arr[i:], n-1):
                yield [arr[i]] + j

p = combi([1, 2, 3, 4, 5], 3)
for i in p:
    print(i)

결과

 

Itertools 패키지

파이썬 라이브러리에서는 itertools 패키지를 지원한다. (약 10배정도 빠르다)

순열

import itertools

arr = [1, 2, 3, 4, 5]
print(*itertools.permutations(arr,3))

결과

조합

import itertools

arr = [1, 2, 3, 4, 5]
print(*itertools.combinations(arr,3))

중복 순열 (곱집합, Cartasian Product)

여러 선언방식들이 존재한다.

import itertools

arr = [1, 2, 3, 4, 5]
print(*itertools.product(arr, repeat=3))

import itertools

arr = [1, 2, 3, 4, 5]
print(*itertools.product(arr, arr, arr))

import itertools

print(*itertools.product(range(1, 6), range(1, 6), range(1, 6)))

중복 조합

import itertools

arr = [1, 2, 3, 4, 5]
print(*itertools.combinations_with_replacement(arr, 3))