[Python] 순열(permutations)과 조합(Combinations) 구현과 라이브러리

순열(permutations)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서대로 나열하는 경우의 수

순열 구현

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 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] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()

    generate([],used)

조합(Combinations)

서로 다른 n개의 원소에서 r개를 뽑는 경우의 수

조합 구현

def combination(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for nxt in range(start, len(arr)):
            if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
                chosen.append(arr[nxt])
                used[nxt] = 1
                generate(chosen)
                chosen.pop()
                used[nxt] = 0
    generate([])

순열, 조합 파이썬 라이브러리

itertools

import itertools
pool = ['A','B','C']
print(list(map("".join, itertools.permutaions(pool, 2)))) # 순열
print(list(map("".join, itertools.combinations(pool, 2)))) # 조합

참고

• https://velog.io/@yeseolee/python%EC%9C%BC%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%A7%81%EC%A0%91-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0