파이썬

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

굴잉 2024. 6. 16. 21:03
728x90

💡 순열 (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)

 

 

🔗 참고 자료

728x90