[Python] 순열, 조합 구현하기

💡 순열 (Permutation)

• n개 중에서 r개를 뽑아 순서대로 나열하는 경우의 수
• nPr = n! / (n-r)!

 

구현방법

• DFS
• 체크리스트-공유된 자원 이용

 

코드

def perm(n, r):
    answer = []

    def gen(choose, checklist):
        if len(choose) == r:
            answer.append(choose.copy())
            return

        for i in range(len(n)):
            if checklist[i] == 0:
                choose.append(n[i])
                checklist[i] = 1
                gen(choose, checklist)
                choose.pop()
                checklist[i] = 0

    gen([], [0] * len(n))

    return answer


result = perm([1, 2, 3], 2)
print(result)

 

 

💡 조합 (Combination)

• n개 중에 순서 상관없이 r개를 고르는 모든 경우의 수
• nCr = nPr / 2!

 

구현 방법

• DFS
• 트리를 트래버스할 때 다음 시작점을 가지고 간다.

코드

def combination(n, r):
    answer = []

    def generate(choose, begin):
        if len(choose) == r:
            answer.append(choose.copy())
            return

        for i in range(begin, len(n)):
            choose.append(n[i])
            generate(choose, i + 1)
            choose.pop()

    generate([], 0)
    return answer

result = combination([1, 2, 3, 4, 5], 2)
print(result)

 

---

 

🔗 참고 자료

• https://www.youtube.com/watch?v=78MHQ9s7kAc
• https://www.youtube.com/watch?v=HYKpunR1Nto