n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수
서로 다른 n개의 원소를 가지고 중복 없이 순서에 상관있게 r개의 원소를 선택 혹은 나열 하는 것
from itertools import combinations
arr = [1, 2, 3]
print(list(combinations(arr, 2)))
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)
- 입력은 순열 때와 같다. 배열도 마찬가지로 정렬한다.
- 조합을 만드는 generate 함수를 만든다. 순열과 마찬가지로 chosen 에 저장된 아이템 개수가 r 개이면 조합이 하나 완성된 것이기 때문에 값을 출력하고 함수를 종료시킨다.
- for 문을 돌리되, 시작을 chosen 에 저장된 마지막 값 다음으로 정한다. 이는 아까 순열함수와 대비되는 부분으로, 조합은 순열과 달리 순서를 고려하지 않고 뽑기 때문에, 가짓수를 제한해줘야 한다. start 가 chosen 이 비어있을 경우 0이 되는 것도 참고한다. 빈값일 때는 그냥 0을 넣어야 한다.
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))
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))