Combination 조합 만들기

조합 combination 

일반적으로 알고리즘 문제를 풀때 보면 조합을 쓰는 경우가 종종 생긴다. 이에 조합을 함수형 프로그래밍으로 구현하는 법과 라이브러리를 사용해서 구하는 법 각각 사용해서 한번 진행해 보겠다. 

 

 

 python 라이브러리 itertools combinations

 

python에서 제공하는 라이브러리 중 itertools라는 것이 있다. 이 tool를 사용하면 쉽게 조합을 구할 수 있다. 우선 조합이란 순서와 관계 없이 차례로 나열 되는 데이터를 구하는 것임을 명심해야 한다. 이제 예제 코드를 보자 

from itertools import permutations, combinations

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

'''
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
[(1, 2, 3, 4)]
'''

예제 결과를 보면 combination( list, n ) 으로 사용되는 것을 확인 할 수 있다. 넣는 값과 몇개의 수로 표현되는지 가지 수를 알려주고 있다. 

 

 함수형 프로그래밍으로 재귀를 사용해 combination 구하기 

재귀로 combination을 만들어 보자. 

 def combination (numbers) :
    if len(numbers) == 0 :
        return [[ ]]
    first = numbers[0]
    rest = numbers[1:]
    com_without_first = combination(rest)
    com_with_first = []

    for cwf in com_without_first:
        _com_with_first = [ *cwf, first]
        com_with_first.append( _com_with_first )
        print( "combination :", *com_with_first)
    

    return [ *com_without_first, *com_with_first ]

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

'''
combination : [4]
combination : [3]
combination : [3] [4, 3]
combination : [2]
combination : [2] [4, 2]
combination : [2] [4, 2] [3, 2]
combination : [2] [4, 2] [3, 2] [4, 3, 2]
combination : [1]
combination : [1] [4, 1]
combination : [1] [4, 1] [3, 1]
combination : [1] [4, 1] [3, 1] [4, 3, 1]
combination : [1] [4, 1] [3, 1] [4, 3, 1] [2, 1]
combination : [1] [4, 1] [3, 1] [4, 3, 1] [2, 1] [4, 2, 1]
combination : [1] [4, 1] [3, 1] [4, 3, 1] [2, 1] [4, 2, 1] [3, 2, 1]
combination : [1] [4, 1] [3, 1] [4, 3, 1] [2, 1] [4, 2, 1] [3, 2, 1] [4, 3, 2, 1]
[[], [4], [3], [4, 3], [2], [4, 2], [3, 2], [4, 3, 2], [1], [4, 1], [3, 1], [4, 3, 1], [2, 1], [4, 2, 1], [3, 2, 1], [4, 3, 2, 1]]
'''

코드를 보면 생각보다 복잡해 보이는데 구획을 나누어서 살펴보자 

if len(numbers) == 0 :
	return [[ ]]
first = numbers[0]
rest = numbers[1:]
com_without_first = combination(rest)

우선 먼저 눈여겨 봐야할 부분은 값을 분리하는 부분이다. first라는 값을 뺀 나머지를 다시 combination함수에 넣는 것을 볼 수 있다. 그리고 이 combination 함수의 처음 if 조건을 보면 값이 없다면 빈 값을 return 해주는 것을 볼 수 있다. 그 다음 코드를 살펴보면 

com_with_first = []

for cwf in com_without_first:
  _com_with_first = [ *cwf, first]
  com_with_first.append( _com_with_first )
  print( "combination :", *com_with_first)

위에서 combination(rest)에 나온 값을 for문을 통해 돌리고 이 값들을 first와 합치는 것을 볼 수 있다. 이 것이 의미하는 바는 만약 combination(rest) 가 [ [], [1] ] 이라면 여기에 각각 [2]를 추가하여 [ [2], [1,2] ] 를 만든 다는 것이다. 

return [ *com_without_first, *com_with_first ]

그리고 마지막을 보면 그렇게 만든  [ [2], [1,2] ] 와 [ [], [1] ] 를 합쳐 최종적으로 [ [], [1], [2], [1,2]] 가 만들어 지게 된다. 

 

combination(n) = combination(n-1) +

                       combination(n-1) * n ( combination(n-1)의 모든 자료에 n을 더한다는 의미이다) 

 

이런 식으로 조합을 만들어 낸다는 뜻이다. 

 

물론 필자는 위와 같은 방식보다는 라이브러리를 사용하는 것을 추천한다. 그러나 만약 라이브러리를 사용하지 못한다면 위와 같은 방법도 좋은 방법이 될 거 같다. 그래서 최종적으로 

def combination (numbers) :
    if len(numbers) == 0 :
        return [[ ]]
    first = numbers[0]
    rest = numbers[1:]
    com_without_first = combination(rest)
    print( "com_without_first" , com_without_first )
    com_with_first = []

    com_with_first = map( lambda x : [*x, first], com_without_first)
    
    return [ *com_without_first, *com_with_first ]

map을 활용하여 좀 더 축약하면 다음과 같은 형식으로 만들어 사용 할 수 있다.