집합의 조합 product in python

 

일반적으로 조합이라고 단순하게 생각해 보면 1개의 집합 데이터가 있는 순열과 조합이 있는데 이것에 대해서는 앞에서 순열과 조합에 대해서 알아보았습니다.

이번에는 집합이 2개 이상일때 조합하는 방법 입니다.

예를 들어 보겠습니다. 아래와 같은 2개의 집합이 있습니다.

A={1,2,3}

B={4,5}

두개의 집합을 조합할때 아래와 같습니다.

{1,4},{1,5},{2,4},{2,5},{3,4},{3,5} 

물론 순서가 없는 경우이기 때문에 조합이라고 할 수 있습니다.

이것을 나타내는 수학적인 용어가 Product 라고 하는데 이미 존재합니다.

이번 시간에는 두개의 집합에 대해서 Product 를 계산하고, 집합이 세개 이상일때 어떻게 하면 될지도 고민해보겠습니다.

집합이 2개인 경우

import itertools

A = [1, 2, 3]
B = [4, 5]

sets = itertools.product(A, B)
for s in sets:
    print(s)

'''
(1, 4)
(1, 5)
(2, 4)
(2, 5)
(3, 4)
(3, 5)
'''

itertools.product 함수를 사용하면 단순합니다.

집합이 3개인 경우

import itertools

A = [1, 2, 3]
B = [4, 5]
C = [6, 7]

sets = itertools.product(A, B, C)
for s in sets:
    print(s)

'''
(1, 4, 6)
(1, 4, 7)
(1, 5, 6)
(1, 5, 7)
(2, 4, 6)
(2, 4, 7)
(2, 5, 6)
(2, 5, 7)
(3, 4, 6)
(3, 4, 7)
(3, 5, 6)
(3, 5, 7)
'''

3개인 경우도 인자를 늘리면 단순합니다.

집합 3개 이상 가변인 경우

import itertools

SET = [[1, 2, 3], [4, 5], [6, 7], [8, 9]]


def product_2(A ,B = []):
    if len(B) == 0:
        return A
    if len(A) == 0:
        return B
    sets = itertools.product(A, B)
    r = []
    for s in sets:
        r.append(s)
    return r

def list_extend(list_of_lists):
    result = []
    for item in list_of_lists:
        if type(item)==tuple or type(item)==list:
            result.extend(item)
        else:
            result.append(item)
    return result

def product_multi(set_list):
    result = []
    for i in range(len(set_list)):
        result = product_2(result, set_list[i])
        if i<=1: continue
        result2 = []
        for rone in result:
            result2.append(list_extend(rone))
        result = result2
    return result

print(product_2([],[1, 2]))
# [1, 2]
print(product_2([1,2],[3]))
# [(1, 3), (2, 3)]
print(product_2([(1, 3), (2, 3)],[4]))
# [((1, 3), 4), ((2, 3), 4)]
print(list_extend(((1, 3), 4)))
# [1, 3, 4]
print(product_multi(SET))
# [[1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 8], [1, 4, 7, 9], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 8], [2, 4, 7, 9], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 8], [2, 5, 7, 9], [3, 4, 6, 8], [3, 4, 6, 9], [3, 4, 7, 8], [3, 4, 7, 9], [3, 5, 6, 8], [3, 5, 6, 9], [3, 5, 7, 8], [3, 5, 7, 9]]

이번에는 제법 복잡한 코드입니다.

하나씩 추가해서 product 를 만들어 냅니다. 그런 후 결과를 펼치게 됩니다.

결과를 펼친다는 의미는 list_extend 를 한다는 의미입니다.

print(list_extend(((1, 3), 4)))
# [1, 3, 4]

즉 (1,3),4 란 결과가 나오면 이것은 (1,3,4)로 만들어야 하기 때문에 결과를 펼치게 됩니다.

최종 구현한 함수는 product_multi 함수를 참고 바랍니다.