Python에서 Powerset 찾기
Hemank Mehtani
2023년1월30일
- 반복적 접근 방식을 사용하여 Python에서 Powerset 가져 오기
-
itertools.combinations함수를 사용하여 Python에서 Powerset 찾기 - 리스트 내포 방법을 사용하여 Python에서 Powerset 찾기
- 재귀 적 방법을 사용하여 Python에서 Powerset 찾기
수학에서 모든 집합의 거듭 제곱 집합은 빈 집합과 함께 주어진 집합의 가능한 모든 하위 집합을 포함하는 집합입니다. 즉, 집합의 모든 하위 집합을 powerset이라고도합니다. Python에는 목록, 집합, 문자열 등의 강력한 집합이있을 수 있습니다.
이 튜토리얼에서 우리는 파이썬에서 주어진 세트의 파워 세트를 찾을 것입니다.
반복적 접근 방식을 사용하여 Python에서 Powerset 가져 오기
재귀 적 접근 방식과 반복적 접근 방식을 모두 사용하여 powerset을 찾을 수 있지만 반복적 접근 방식이 더 빠른 프로세스이므로 반복적 접근 방식보다 선호됩니다.
이러한 powerset을 생성하기 위해 중첩for루프를 사용합니다.
예를 들면
def powerset(fullset):
listsub = list(fullset)
subsets = []
for i in range(2 ** len(listsub)):
subset = []
for k in range(len(listsub)):
if i & 1 << k:
subset.append(listsub[k])
subsets.append(subset)
return subsets
subsets = powerset(set([1, 2, 3, 4]))
print(subsets)
print(len(subsets))
출력:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
16
itertools.combinations함수를 사용하여 Python에서 Powerset 찾기
itertools는 데이터 구조를 반복하는 데 사용되는 Python의 모듈입니다. 이러한 데이터 구조를 iterable이라고도합니다. for-loop를 사용하여 넘어갈 수 있습니다.
이 모듈의combinations기능은 세트의 조합을 생성하여 powerset을 생성 할 수 있습니다.
아래 코드를 참조하십시오.
from itertools import combinations
def powerset(string):
n = len(string)
for i in range(0, n + 1):
for element in combinations(string, i):
print("".join(element))
string = ["x", "y", "z"]
powerset(string)
출력:
x
y
z
xy
xz
yz
xyz
리스트 내포 방법을 사용하여 Python에서 Powerset 찾기
리스트 내포은 기존 목록을 기반으로 새 목록을 만드는 방법입니다. 목록을 만드는 데 사용되는 다른 함수 및 루프보다 더 작고 빠른 더 짧은 구문을 제공합니다.
이 메서드에서도 중첩for루프를 사용합니다.
예를 들면
def get_subsets(fullset):
listrep = list(fullset)
n = len(listrep)
return [[listrep[k] for k in range(n) if i & 1 << k] for i in range(2 ** n)]
string = ["x", "y", "z"]
print(get_subsets(string))
출력:
[[], ['x'], ['y'], ['x', 'y'], ['z'], ['x', 'z'], ['y', 'z'], ['x', 'y', 'z']]
재귀 적 방법을 사용하여 Python에서 Powerset 찾기
재귀 메서드는 함수가 다른 인수를 사용하여 자신을 계속 호출하는 메서드입니다. 집합의 거듭 제곱을 찾기 위해 재귀 함수를 만들 수 있습니다.
예를 들면
def powerSet(string, index, c):
if index == len(string):
print(c)
return
powerSet(string, index + 1, c + string[index])
powerSet(string, index + 1, c)
s1 = ["a", "b", "c"]
index = 0
c = ""
powerSet(s1, index, c)
출력:
abc
ab
ac
a
bc
b
c