[Python] 다중합집합, 다중교집합

다중집합(Multi Set)

기존의 집합과 다르게 중복된 원소를 허용하는 집합을 다중집합이라고 한다.
중복집합이라고도 불리며, 통상적인 집합은 각 원소의 중복도가 1인 중복집합으로 여길 수 있다.

a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]

일반 집합의 합집합: [1,2,3,4,5,6]
일반 집합의 교집합: [1,2,3,4]

다중 집합의 합집합: [1,1,2,2,3,4,5,6]
다중 집합의 교집합: [1,2,3,4]

 
 

기존의 python에서 일반적인 합집합, 교집합을 구현할 때는 set을 이용해 원소의 중복을 허용하지 않았다.

a=[1,2,3,4,5]
b=[2,4,5,7,8]

x = list(set(a) | set(b)) # 합집합

x = [1,2,3,4,5,7,8]

a = [1,2,3,4,5]
b = [2,4,5,7,8]

x = list(set(a) & set(b)) # 교집합

x = [2,4,5]

그러나 다중집합에서는 원소의 중복허용이 포인트이기 때문에 set이 아닌 다른 방법으로 다중집합의 합집합, 교집합을 구현해야 한다.

 

다중합집합

다중합집합도 일반적인 합집합과 마찬가지로 (a의 차집합 + b의 차집합 + a와b의 교집합) 이런 형태로 이루어져 있다.

a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]

a의 차집합 : [2,5]
b의 차집합 : [1,6]
a와 b의 다중교집합 : [1,2,3,4]
a와 b의 다중합집합 : [1,1,2,2,3,4,5,6]

a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]

a_temp = a.copy()
a_result = a.copy()

for i in b:
    if i not in a_temp:
        a_result.append(i) # b에 있지만 a에 없는건 b의 차집합이므로 원소를 a에 더함
    else:
        a_temp.remove(i) # a_temp는 a의 차집합, 중복되는 원소 때문에 remove가 필요

    
print(a_result)

집합a는 이미 a의 차집합과 a와b의 교집합의 합으로 이루어져 있기 때문에, a에 b의 차집합만 더하면 된다.
a_temp.remove(i) 이 코드가 중요한데 중복된 원소가 핵심이므로 중복된 원소를 없애기 위해 복사본을 만들어서 remove를 했다.

 

다중교집합

a와 b를 비교해 중복되는 원소면 제거하고 제거한 원소를 다른 배열에 넣으면 된다.

a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]

result = []

for i in b:
    if i in a:
        a.remove(i)
        gyo_result.append(i)
            
print(result)