Python : 순열과 조합

library 이용하기

from itertools import permutations
ls = [1,2,3,4]
print(list(permutations(ls, 2)))
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

from itertools import combinations
ls = [1,2,3,4]
print(list(combinations(ls, 2)))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

코드로 구현하기

Permutation

1. used 배열을 통해 이미 arr에 존재하는 지를 확인
   만약 arr에 존재하지 않는다면
   chosen에 해당 숫자를 추가하여 used[i]를 True로 변경시키고,
   새로운 chosen에 대하여 generate()를 순회시킨 후
   chosen에서 해당 숫자를 제거하고 used[i]를 다시 False로 변경

def permutation(arr, r):
    used = [False for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return
        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = True
                generate(chosen, used)
                used[i] = False
                chosen.pop()

    generate([], used)

# permutation([1,2,3,4], 2)

Combination

Permutation과 굉장히 유사하다.
Permutation에서는 used를 이용하여 이미 배열에 존재하지 않는 수들에 대해 모두 combination()을 돌렸지만,
Combination에서는 index를 이용하여 배열의 마지막 index보다 큰 index들만 배열에 넣어줬다.

def combination(arr, r):

    def generate(chosen):
        if len(chosen) == r:
            ls = [x for i,x in enumerate(arr) if i in chosen]
            print(ls)
            return
        for i in range(len(arr)):
            if chosen[-1] < i:
                generate(chosen + [i])

    for i in range(len(arr)):
        generate([i])

combination([1,2,3,4], 2)