순열과 조합

1. 순열

1.1 반복문 이용

isUse = [False] * 4
set = []

for i in range(4):
    if isUse[i]:
        continue
    isUse[i] = True
    for j in range(4):
        if isUse[j]:
            continue
        isUse[j] = True
        for k in range(4):
            if isUse[k]:
                continue
            isUse[k] = True

            tmp = arr[i], arr[j], arr[k]
            set.append(tmp)

            isUse[k] = False
        isUse[j] = False
    isUse[i] = False

입력 : [1, 2, 3, 4]

출력
(1, 2, 3) (1, 2, 4) (1, 3, 2)
(1, 3, 4) (1, 4, 2) (1, 4, 3)
(2, 1, 3) (2, 1, 4) (2, 3, 1)
(2, 3, 4) (2, 4, 1) (2, 4, 3)
(3, 1, 2) (3, 1, 4) (3, 2, 1)
(3, 2, 4) (3, 4, 1) (3, 4, 2)
(4, 1, 2) (4, 1, 3) (4, 2, 1)
(4, 2, 3) (4, 3, 1) (4, 3, 2)

반복문을 이용해서 순열을 쉽게 구할 수 있지만, 위으 예처럼 4개 중에 3개가 아닌 훨씬 더 큰 경우의 수를 구하려면 코드가 굉장이 길어진다. 재귀 함수를 이용하면 순열의 개수에 상관없이 일정한 코드를 사용할 수 있다.

1.2 재귀 이용

import copy
set = []
tmp = []  # 수를 저장할 배열

def Permutation(cnt):
    if len(tmp) == cnt:
        made = copy.deepcopy(tmp)
        set.append(made)
        return

    for i in range(4):
        if arr[i] in tmp:
            continue
        tmp.append(arr[i])
        Permutation(cnt)
        tmp.pop()
Permutation(3)

입력 : [1, 2, 3, 4]

출력
(1, 2, 3) (1, 2, 4) (1, 3, 2)
(1, 3, 4) (1, 4, 2) (1, 4, 3)
(2, 1, 3) (2, 1, 4) (2, 3, 1)
(2, 3, 4) (2, 4, 1) (2, 4, 3)
(3, 1, 2) (3, 1, 4) (3, 2, 1)
(3, 2, 4) (3, 4, 1) (3, 4, 2)
(4, 1, 2) (4, 1, 3) (4, 2, 1)
(4, 2, 3) (4, 3, 1) (4, 3, 2)

2. 조합

2.1 반복문 이용

set = []

for i in range(4):
    for j in range(i+1, 4):
        for k in range(j+1, 4):
            tmp = arr[i], arr[j], arr[k]
            set.append(tmp)

입력 : [1, 2, 3, 4]

출력 : (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

순열과 다르게 조합은 순서에 상관이 없다. 직전 반복문에서 사용한 숫자를 다시 사용하지 않기 위해서 바로 다음 요소부터 반복문을 수행하도록 순서를 강제해야 한다.

2.2 재귀 이용

import copy
tmp = []
set = []

def Combination(idx, cnt):
    if len(tmp) == cnt:
        made = copy.deepcopy(tmp)
        set.append(made)
        return

    for i in range(idx, 4):
        tmp.append(arr[i])
        Combination(i+1, cnt)
        tmp.pop()

Combination(0, 3)

입력 : [1, 2, 3, 4]

출력 : (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)