부분집합 구하기 with Python

def subSet(uSet, n, mSet=set(), rSet=set()):
    if n == 0:
        rSet.add(tuple(mSet))

    for i in range(len(uSet)):
        tmpSet = mSet.copy()
        tmpSet.add(uSet[i])
        if (n-1 >= 0):
            subSet(uSet[i+1:], n-1, tmpSet, rSet)

    return rSet
    

A = ["A", "B", "C", "D"]

print(subSet(A, 3))

제 마음대로 짜서 정석은 아닙니다.

구현원리는 다음과 같습니다.

 

U = { A, B, C, D } 일 때 길이가 1인 부분집합을 구하는 건 어렵지 않습니다.

이를 전제로 길이가 3일 때를 생각해 봅니다.

 

U = { A, B, C, D } 일 때, 길이가 3인 부분집합은 { ABC, ABD, ACD, BCD } 입니다.

A를 무조건 포함하는 길이가 3인 부분집합은 { ABC, ABD, ACD } 입니다.

A를 제외하고 본다면 { BC, BD, CD } 입니다. 이는 U = { B, C, D } 일 때, 길이가 2인 부분집합과 같습니다.

 

길이가 3일 경우는 제껴두고,

U = { B, C, D } 일 때, 길이가 2인 부분집합을 구하는 것에 대해 생각해 봅니다.

 

 

U = { B, C, D } 일 때, 길이가 2인 부분집합은 { BC, BD, CD } 입니다.

B를 무조건 포함하는 길이가 2인 부분집합은 { BC, BD } 입니다.

B를 제외하고 본다면 { C, D } 입니다. 이는 U = { C, D } 일 때, 길이가 1인 부분집합과 같습니다.

위에서 길이가 1인 부분집합을 구하는건 어렵지 않다고 했기 때문에 B를 무조건 포함하는 길이가 2인 부분 집합은 쉽게 구할 수 있습니다.

 

하지만 아직 끝난건 아닙니다.

B를 무조건 포함하는 경우를 구했으니 C를 무조건 포함하는 경우와 D를 무조건 포함하는 경우 또한 구해야합니다. 

 

C의 경우는,

U = { B, C, D } 일 때,

C를 무조건 포함하는 길이가 2인 부분집합은 { BC, CD } 입니다.

C를 제외하고 본다면 { B, D } 입니다. 마찬가지로 U = { B, D } 일 때, 길이가 1인 부분집합과 같습니다.

하지만 B를 포함하는 경우는 위에서 구했으니 U = { D } 일 때만 구해도 되겠군요.

 

D를 무조건 포함하는 길이가 2인 부분집합은 { BD, CD } 입니다.

D를 제외하고 본다면 { B, C } 이지만, B와 C를 포함하는 경우는 모두 구했기 때문에 공집합이 됩니다.

 

이렇게 U = { B, C, D } 일 때, 길이가 2인 부분 집합은

B를 무조건 포함하는 길이가 2인 부분집합인 { BC, BD } 와

C를 무조건 포함하는 길이가 2인 부분집합에서 B를 포함하는 경우를 제외한 { CD } 와

D를 무조건 포함하는 길이가 2인 부분집합에서 B와 C를 포함하는 경우를 제외한 공집합을 더하면

{ BC, BD, CD } 입니다.

 

이런식으로 풀면 되는데 글로 설명하려니 쉽지 않네요.

길이가 1인 부분 집합을 구하는건 어렵지 않으니,

길이가 1일 때까지 길이를 계속 줄여나간다는게 포인트입니다.