[Python] 완전 탐색 알고리즘 - 조합

조합(Combinations)

개념

n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수

서로 다른 n개의 원소를 가지고 중복 없이 순서에 상관있게 r개의 원소를 선택 혹은 나열 하는 것

• ex)
  
  Input: [1, 2, 3]
  Output: [ [1, 2], [1, 3], [2, 3] ]

코드

Git - 코드

방법 0 - 라이브러리 사용

from itertools import combinations

arr = [1, 2, 3]
print(list(combinations(arr, 2)))

---

방법 1 - 알고리즘

def combination(arr, r):
    # 1.
    arr = sorted(arr)

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

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

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

1. 입력은 순열 때와 같다. 배열도 마찬가지로 정렬한다.
2. 조합을 만드는 generate 함수를 만든다. 순열과 마찬가지로 chosen 에 저장된 아이템 개수가 r 개이면 조합이 하나 완성된 것이기 때문에 값을 출력하고 함수를 종료시킨다.
3. for 문을 돌리되, 시작을 chosen 에 저장된 마지막 값 다음으로 정한다. 이는 아까 순열함수와 대비되는 부분으로, 조합은 순열과 달리 순서를 고려하지 않고 뽑기 때문에, 가짓수를 제한해줘야 한다. start 가 chosen 이 비어있을 경우 0이 되는 것도 참고한다. 빈값일 때는 그냥 0을 넣어야 한다.

출처

방법 1 - 과정

---

방법 2 - 알고리즘

def gen_combinations(arr, n):
    result =[] 

    if n == 0: 
        return [[]]

    for i in range(0, len(arr)): 
        elem = arr[i] 
        rest_arr = arr[i + 1:] 
        # print("rest_arr=")
        # print(rest_arr)
        for C in gen_combinations(rest_arr, n-1):
            # print(elem)
            # print(C)
            result.append([elem]+C)
            # print("result=")
            # print(result)
              
    return result

print(gen_combinations([1, 2, 3], 2))

출처

방법 2 - 과정

---

경우의 수

def choose(n,k):
    if k == 0: 
       return 1
    elif n < k:
       return 0
    else:
        return choose(n-1, k-1) + choose(n-1, k)

print(choose(3,2))

출처