🧮 부분 집합, 멱집합 구하기 알고리즘 직접 구현!

부분집합, 멱집합을 구하는 알고리즘을 파이썬으로 구현해보자.

 

부분 집합, 멱 집합이란?

• 부분 집합은 어떤 집합에서 몇몇 원소들만 뽑아서 만든 집합. 부분 집합은 원래 집합에 포함되는 관계이다.
• 멱집합은 어떤 집합의 모든 부분 집합을 모아둔 집합
• 원소 갯수가 n인 원래 집합에서 원소 갯수가 r인 부분집합의 갯수는 nCr(조합)과 같다.
• 멱집합 원소의 갯수는 2^n이다.

 

부분 집합, 멱집합 알고리즘 구현해보기

부분 집합

조합을 구하는 방법과 같다. 아래 글 참고.

🧮 조합 알고리즘 직접 구현!

 

멱집합

비트 마스크 이용하기

def power_set(arr):
    n = len(arr)
    result = []

    for mask in range(1<<n):
        subset = set()
        i = 0

        while mask:
            if mask & 1:
                subset.add(arr[i])
            i += 1
            mask >>= 1

        result.append(subset)

    return result

print(power_set([1,2,3]))

어떤 순서의 원소가 포함되면 1, 포함되지 않으면 0으로 따져보자. 그러면 해당 부분 집합은 2진법으로 표현 가능하다.

 

재귀 이용하기

def power_set(arr):
    if arr == []:
        return [set()]

    new_arr = arr.copy()
    item = new_arr.pop()

    not_inclue_pset = power_set(new_arr)
    inclute_pset = [s | {item} for s in not_inclue_pset]

    return not_inclue_pset + inclute_pset


print(power_set([1, 2, 3]))

 특정 원소가 포함된 부분 집합들의 집합은 특정 원소가 없는 집합의 멱집합에 특정 원소를 포함시켜준 것과 같다. 따라서 원소를 하나 뺀 후 나머지에 대해 멱집합을 구해주는 재귀를 이용하여 구해준다.

 

조합 이용하기

def power_set(arr):
    n = len(arr)
    result = []

    for r in range(0, n+1):
        result += combination(arr, r)

    return result
    
print(power_set([1, 2, 3]))

 조합에서 뽑는 원소 갯수가 0부터 n일때까지를 모두 더하면 멱집합과 같게 된다. 지난 시간에 만든 조합 알고리즘 함수를 재이용하여 다음과 같이 쓸 수도 있다.