파이썬으로 특정 크기의 집합에서 모든 부분집합 구하는 방법

이 글에서는 주어진 집합에서 특정 크기(n)를 가지는 모든 부분집합을 구하는 문제와 그 해결 방법을 알아보겠습니다.

문제 정의

문제: 하나의 집합이 주어졌을 때, 크기가 n인 모든 부분집합을 나열해야 합니다.

예를 들어 집합 {1, 2, 3, 4, 5}에서 크기가 4인 부분집합을 모두 찾는 경우를 생각해 볼 수 있습니다. 이 문제는 파이썬의 itertools 모듈을 활용하면 매우 간단하게 해결할 수 있으며, 아래에서 세 가지 접근 방식을 소개합니다.

방법 1: itertools.combinations() 사용하기

가장 기본적인 방법은 itertools.combinations() 함수를 직접 호출하는 것입니다. 이 함수는 입력된 반복 가능한 객체에서 지정한 길이만큼의 모든 조합을 튜플 형태로 반환합니다.

예제 코드

# itertools 모듈 임포트
import itertools

def findsubsets(s, n):
    return list(itertools.combinations(s, n))

# 메인 코드
s = {1, 2, 3, 4, 5}
n = 4
print(findsubsets(s, n))

실행 결과

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

결과를 보면 각 부분집합이 튜플(tuple) 형태로 반환되는 것을 확인할 수 있습니다.

방법 2: map()과 combinations() 조합하기

결괏값을 튜플이 아닌 집합(set) 형태로 얻고 싶다면 map() 함수를 함께 사용할 수 있습니다. 각 조합에 set 생성자를 적용하여 결과를 집합 타입으로 변환합니다.

예제 코드

# itertools 모듈에서 combinations만 임포트
from itertools import combinations

def findsubsets(s, n):
    return list(map(set, itertools.combinations(s, n)))

# 드라이버 코드
s = {1, 2, 3, 4, 5}
n = 4
print(findsubsets(s, n))

실행 결과

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

이번에는 각 부분집합이 중괄호로 표시되는 집합 객체로 반환된 것을 볼 수 있습니다.

방법 3: 리스트 컴프리헨션 활용하기

세 번째 방법은 파이썬다운 문법인 리스트 컴프리헨션(list comprehension)을 사용하는 것입니다. 코드가 더 간결하고 가독성이 뛰어나 많은 개발자들이 선호하는 방식입니다.

예제 코드

# itertools 모듈 임포트
import itertools

def findsubsets(s, n):
    return [set(i) for i in itertools.combinations(s, n)]

# 드라이버 코드
s = {1, 2, 3, 4, 5}
n = 4
print(findsubsets(s, n))

실행 결과

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

마무리

지금까지 파이썬에서 주어진 집합의 특정 크기를 가지는 모든 부분집합을 구하는 세 가지 방법을 살펴보았습니다. itertools.combinations()를 단독으로 사용하면 튜플 리스트를 얻을 수 있고, map() 또는 리스트 컴프리헨션과 결합하면 집합 형태의 결과를 손쉽게 얻을 수 있습니다. 상황에 맞는 방법을 선택하여 활용해 보시기 바랍니다.