[python] combinations with replacement(중복조합) 구현하기 - itertools, recursion

skdus·2022년 1월 16일
0

Algorithms

목록 보기
3/6
post-thumbnail

✍중복조합이란?

중복 조합이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미 (순서 상관 없음)

n=2, k=3일 경우, 2+(3-1)C3 = 4C3 = 4! = 24이다.
n=3, k=3일 경우, 5C3 = 10이다.
-> [0, 0, 0][0, 0, 1][0, 0, 2][0, 1, 1][0, 1, 2][0, 2, 2][1, 1, 1][1, 1, 2][1, 2, 2][2, 2, 2]


✍itertools를 사용한 중복조합

from itertools import combinations_with_replacement

arr = [1,2,3]

for i in combinations_with_replacement(arr,3):
    print(i, end=" ")

✍recursion를 사용한 중복조합


그림은 n=3, k=3인 경우이다.
그림을 보면, level마다 시작점은 제각각이지만, 끝점은 다 똑같다. (조합과 다른점)
그러므로 시작점은 받아오고 끝점은 데이터의 개수만큼 지정해주면 된다.

시작점이 다 다른 것을 보면 알 수 있듯이, 조합과 달리 중복조합은 전에 선택된 것부터 시작점으로 선택할 수 있다.

n, k = 3,3
A = ['귤', '감', '배']
arr = [0]*k

def combi(level, start):
  #종료조건
  if level >= k:
    print(arr)
    return
  
  for i in range(start, len(A)):
    arr[level] = A[i]
    combi(level+1, i)

combi(0,0)

✍후기

조합을 구현할 때는 이해가 잘 가지않아 어려웠는데, 조합과 중복조합의 차이를 알고 푸니 좀 더 쉽게 이해할 수 있었다. 문제를 제대로 파악하는 것이 가장 중요한 것 같다.

코드 보러가기 👉 combination_with_repetition.py
피드백은 언제나 환영입니다.💛

[참고사이트]
https://www.youtube.com/watch?v=3r1vEOy3uCQ&list=PLnp1rUgG4UVYc77Ltm9Le6LtHc71jY390&index=16

0개의 댓글