집합의 모든 하위 집합을 가져오는 방법?(전원 설정)
한 세트가 주어짐
{0, 1, 2, 3}
하위 집합을 생성하는 방법:
[set(),
{0},
{1},
{2},
{3},
{0, 1},
{0, 2},
{0, 3},
{1, 2},
{1, 3},
{2, 3},
{0, 1, 2},
{0, 1, 3},
{0, 2, 3},
{1, 2, 3},
{0, 1, 2, 3}]
Python 페이지에는 정확히powerset이것에 대한 레시피:
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
출력:
>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]
처음에 빈 튜플이 마음에 들지 않으면 그냥 변경할 수 있습니다.range에 대한 .range(1, len(s)+1)길이가 0인 조합을 방지합니다.
여기 파워 세트에 대한 코드가 더 있습니다.이것은 처음부터 작성된 것입니다.
>>> def powerset(s):
... x = len(s)
... for i in range(1 << x):
... print [s[j] for j in range(x) if (i & (1 << j))]
...
>>> powerset([4,5,6])
[]
[4]
[5]
[4, 5]
[6]
[4, 6]
[5, 6]
[4, 5, 6]
빈에 들지 on제 경우 Rushakoff를 는 범위 문을 범위( "처음에 빈 튜플이 마음에 들지 않으면 on."저의 경우 변경하지 않는 한 범위 문을 범위(1, len(s)+1)로 변경하면 됩니다."for i in range(1 << x)for i in range(1, 1 << x).
몇 년이 지난 지금, 저는 다음과 같이 쓰고 있습니다.
def powerset(s):
x = len(s)
masks = [1 << i for i in range(x)]
for i in range(1 << x):
yield [ss for mask, ss in zip(masks, s) if i & mask]
그리고 테스트 코드는 다음과 같습니다.
print(list(powerset([4, 5, 6])))
용사를 합니다.yield즉, 단일 메모리에서 모든 결과를 계산할 필요가 없습니다.주 루프 외부의 마스크를 사전 계산하는 것은 가치 있는 최적화로 간주됩니다.
빠른 답을 찾고 있다면, 저는 방금 구글에서 "파이썬 파워 세트"를 검색했고 다음과 같은 것을 생각해냈습니다.Python Power Set Generator
다음은 해당 페이지의 코드에서 복사 붙여넣기입니다.
def powerset(seq):
"""
Returns all the subsets of this set. This is a generator.
"""
if len(seq) <= 1:
yield seq
yield []
else:
for item in powerset(seq[1:]):
yield [seq[0]]+item
yield item
다음과 같이 사용할 수 있습니다.
l = [1, 2, 3, 4]
r = [x for x in powerset(l)]
지금은 원하는 모든 요소의 목록이며 정렬 및 인쇄할 수 있습니다.
r.sort()
print r
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
패키지의 함수를 사용합니다.
반복 가능한 모든 부분 집합을 생성합니다.
>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
세트를 사용하려면 다음을 사용합니다.
list(map(set, powerset(iterable)))
저는 다음 알고리즘이 매우 명확하고 간단하다는 것을 알게 되었습니다.
def get_powerset(some_list):
"""Returns all subsets of size 0 - len(some_list) for some_list"""
if len(some_list) == 0:
return [[]]
subsets = []
first_element = some_list[0]
remaining_list = some_list[1:]
# Strategy: get all the subsets of remaining_list. For each
# of those subsets, a full subset list will contain both
# the original subset as well as a version of the subset
# that contains first_element
for partial_subset in get_powerset(remaining_list):
subsets.append(partial_subset)
subsets.append(partial_subset[:] + [first_element])
return subsets
할 수 또 하는 입니다.n 으로서 트로 합니다. 검정력으로 설정된 숫자의 양은n는 자수는입니다.2 ^ n이 알고리즘의 원리는 요소가 부분 집합에 존재하거나 존재하지 않을 수 있고 이진 숫자가 1 또는 0일 수 있지만 둘 다 될 수 없다는 것입니다.
def power_set(items):
N = len(items)
# enumerate the 2 ** N possible combinations
for i in range(2 ** N):
combo = []
for j in range(N):
# test bit jth of integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo
저는 MITx를 수강할 때 두 알고리즘을 발견했습니다: 6.00.2x 컴퓨터 사고와 데이터 과학 입문. 그리고 저는 이것이 제가 본 것 중 가장 이해하기 쉬운 알고리즘 중 하나라고 생각합니다.
from functools import reduce
def powerset(lst):
return reduce(lambda result, x: result + [subset + [x] for subset in result],
lst, [[]])
파워 세트의 개선이 있습니다.
def powerset(seq):
"""
Returns all the subsets of this set. This is a generator.
"""
if len(seq) <= 0:
yield []
else:
for item in powerset(seq[1:]):
yield [seq[0]]+item
yield item
TL;DR(간소화로 직접 이동)
이전에 답변을 추가했지만, 새로운 구현이 정말 마음에 듭니다.저는 한 세트를 입력으로 사용하고 있지만, 실제로는 어떤 반복 가능한 것일 수 있습니다. 그리고 저는 입력의 거듭제곱인 한 세트를 반환합니다.저는 이 접근 방식이 검정력 집합(모든 부분 집합 집합)의 수학적 정의와 더 일치하기 때문에 좋아합니다.
def power_set(A):
"""A is an iterable (list, tuple, set, str, etc)
returns a set which is the power set of A."""
length = len(A)
l = [a for a in A]
ps = set()
for i in range(2 ** length):
selector = f'{i:0{length}b}'
subset = {l[j] for j, bit in enumerate(selector) if bit == '1'}
ps.add(frozenset(subset))
return ps
답변에 게시한 출력이 정확하게 필요한 경우 다음을 사용합니다.
>>> [set(s) for s in power_set({1, 2, 3, 4})]
[{3, 4},
{2},
{1, 4},
{2, 3, 4},
{2, 3},
{1, 2, 4},
{1, 2},
{1, 2, 3},
{3},
{2, 4},
{1},
{1, 2, 3, 4},
set(),
{1, 3},
{1, 3, 4},
{4}]
설명.
는 멱집합의 멱집합인 것으로 있습니다.2 ** len(A)그래서 그것은 분명히 볼 수 있습니다.for 루우프
입력(이상적으로 집합)을 목록으로 변환해야 하는데, 이는 집합이 고유한 순서가 없는 요소의 데이터 구조이기 때문이며, 순서가 하위 집합을 생성하는 데 중요하기 때문입니다.
selector이 알고리즘의 핵심입니다.:selector는 입력 집합과 길이가 같고, 이를 가능하게 하기 위해 패딩이 있는 f-string을 사용하고 있습니다.기본적으로 각 반복 중에 각 하위 집합에 추가할 요소를 선택할 수 있습니다.의 요소가 {0, 1, 2}따라서 선택기는 0과 7 사이의 값을 취합니다(2진수). 이 값은 다음과 같습니다.
000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7
따라서 각 비트는 원래 세트의 요소를 추가해야 하는지 여부를 나타내는 표시기 역할을 할 수 있습니다.이진수들을 보고, 각각의 숫자들을 단지 슈퍼 세트의 요소로서 생각하세요.1지수에 있는 원소를 의미합니다.j추가해야 , 추해야합니다가다합▁should▁added.0이 요소를 추가하지 않아야 함을 의미합니다.
는 각, 이 을 는나각 반복서생집부합위사성집이, 변다니합환집을합고하부분용를이해해하합기을로 합니다.frozenset에 추가할 수 있습니다.ps(전원 설정).그렇지 않으면 Python의 집합은 불변 객체로만 구성되어 있기 때문에 추가할 수 없습니다.
단순화
일부 파이썬 이해를 사용하여 코드를 단순화할 수 있으므로 루프에 대한 이해를 제거할 수 있습니다.사용할 수도 있습니다.zip사용을 피하기 위해j인덱스와 코드는 다음과 같이 됩니다.
def power_set(A):
length = len(A)
return {
frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'})
for i in range(2 ** length)
}
바로 그겁니다.제가 이 알고리즘을 좋아하는 것은 다른 알고리즘보다 더 명확하고 직관적이라는 것입니다. 왜냐하면 의존하는 것은 꽤 마법처럼 보이기 때문입니다.itertools예상대로 작동하지만 말입니다.
이 작업은 매우 자연스럽게 수행할 수 있습니다.itertools.product:
import itertools
def powerset(l):
for sl in itertools.product(*[[[], [i]] for i in l]):
yield {j for i in sl for j in i}
def get_power_set(s):
power_set=[[]]
for elem in s:
# iterate over the sub sets so far
for sub_set in power_set:
# add a new subset consisting of the subset at hand added elem to it
# effectively doubling the sets resulting in the 2^n sets in the powerset of s.
power_set=power_set+[list(sub_set)+[elem]]
return power_set
예:
get_power_set([1,2,3])
수확량
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
너무 늦은 거 알아요
이미 많은 다른 해결책들이 있지만 여전히...
def power_set(lst):
pw_set = [[]]
for i in range(0,len(lst)):
for j in range(0,len(pw_set)):
ele = pw_set[j].copy()
ele = ele + [lst[i]]
pw_set = pw_set + [ele]
return pw_set
저는 그저 가장 이해하기 쉬운 해결책, 안티코드 골프 버전을 제공하고 싶었습니다.
from itertools import combinations
l = ["x", "y", "z", ]
def powerset(items):
combo = []
for r in range(len(items) + 1):
#use a list to coerce a actual list from the combinations generator
combo.append(list(combinations(items,r)))
return combo
l_powerset = powerset(l)
for i, item in enumerate(l_powerset):
print "All sets of length ", i
print item
그 결과들
길이 0의 모든 세트
[()]
길이 1의 모든 세트
[('x',), ('y',), ('z',)]
길이 2의 모든 세트
[('x', 'y'), ('x', 'z'), ('y', 'z')]
길이 3의 모든 세트
[('x', 'y', 'z')]
자세한 내용은 iter tools 문서, 파워 세트에 대한 위키백과 항목을 참조하십시오.
모든 부분 집합의 일부인 빈 집합을 사용하면 다음을 사용할 수 있습니다.
def subsets(iterable):
for n in range(len(iterable) + 1):
yield from combinations(iterable, n)
from itertools import combinations
def subsets(arr: set) -> list:
subsets = []
[subsets.extend(list(combinations(arr,n))) for n in range(len(arr))]
return subsets
a = {1,2,3}
print(subsets(a))
출력:
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3)]
정렬된 하위 집합의 경우 다음 작업을 수행할 수 있습니다.
# sorted subsets
print(sorted(subsets(a)))
출력:
[(), (1,), (1, 2), (1, 3), (2,), (2, 3), (3,)]
빠른 파워 세트 리프레셔!
집합 X의 거듭제곱 집합은 단순히 빈 집합을 포함한 X의 모든 부분 집합입니다.
예제 집합 X = (a,b,c)
전원 집합 = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, {c}, {} }
다음은 전력 세트를 찾는 또 다른 방법입니다.
def power_set(input):
# returns a list of all subsets of the list a
if (len(input) == 0):
return [[]]
else:
main_subset = [ ]
for small_subset in power_set(input[1:]):
main_subset += [small_subset]
main_subset += [[input[0]] + small_subset]
return main_subset
print(power_set([0,1,2,3]))
출처에 대한 전적인 신용
특정 길이의 부분 집합을 원하는 경우 다음과 같이 수행할 수 있습니다.
from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])
일반적으로 임의 길이 부분 집합의 경우 범위 인수를 수정할 수 있습니다.출력은
[(), (0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), (0, 1, 2, 3)]
다음과 같이 할 수 있습니다.
def powerset(x):
m=[]
if not x:
m.append(x)
else:
A = x[0]
B = x[1:]
for z in powerset(B):
m.append(z)
r = [A] + z
m.append(r)
return m
print(powerset([1, 2, 3, 4]))
출력:
[[], [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]]
def powerSet(s):
sets = [[]]
for i in s:
newsets = []
for k in sets:
newsets.append(k+[i])
sets += newsets
return sets
간단한 답을 원하는 사람들을 위해 먼저 코드를 작성합니다.여기에 좋은 설명이 있습니다. https://leetcode.com/problems/subsets/solutions/3138042/simple-python-solution/
그러나 간단한 대답은 빈 집합의 집합, 즉 "sets = []"부터 시작한다는 것입니다."for i in s", 즉 "print(set)" 아래에 문을 인쇄하고 각 요소에 대해 두 배가 되는지 확인할 것을 권장합니다.
간단한 방법은 2의 보완 산술에서 정수의 내부 표현을 활용하는 것입니다.
정수의 이진수 표현은 0에서 7 사이의 숫자에 대해 {000, 001, 010, 011, 100, 101, 110, 111}과 같습니다.정수 카운터 값의 경우, 1을 집합에 해당하는 요소의 포함으로, '0'을 제외로 고려하면 계수 시퀀스를 기반으로 하위 집합을 생성할 수 있습니다.는 다에서숫생합니다야성에서 .0pow(2,n) -1여기서 n은 배열의 길이, 즉 이진 표현의 비트 수입니다.
이를 기반으로 한 간단한 서브셋 생성기 함수는 다음과 같이 작성할 수 있습니다.그것은 기본적으로 의존합니다.
def subsets(array):
if not array:
return
else:
length = len(array)
for max_int in range(0x1 << length):
subset = []
for i in range(length):
if max_int & (0x1 << i):
subset.append(array[i])
yield subset
그리고 나서 그것은 사용될 수 있습니다.
def get_subsets(array):
powerset = []
for i in subsets(array):
powerser.append(i)
return powerset
테스트
로컬 파일에 다음을 추가하는 중
if __name__ == '__main__':
sample = ['b', 'd', 'f']
for i in range(len(sample)):
print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])
다음과 같은 출력을 제공합니다.
Subsets for ['b', 'd', 'f'] are [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']]
Subsets for ['d', 'f'] are [[], ['d'], ['f'], ['d', 'f']]
Subsets for ['f'] are [[], ['f']]
이 답변들의 거의 대부분은 다음을 사용합니다.listset그건 제게 사기꾼처럼 느껴졌어요그래서, 호기심 때문에 저는 정말로 간단한 버전을 하려고 했습니다.set다른 "파이썬 신규" 사용자를 위해 요약합니다.
Python의 세트 구현을 처리하는 데 몇 가지 이상한 점이 있다는 것을 알게 되었습니다.저에게 가장 놀라운 것은 빈 세트를 다루는 것이었습니다.이것은 Ruby's Set 구현과는 대조적으로 간단하게 할 수 있습니다.Set[Set[]]그리고 a를 얻습니다.Set의 빈 포는하함것을빈을 Set그래서 처음에는 조금 혼란스러웠습니다.
검하기중을 할 때 , 수행토.powerset와 함께set 저는 두 문제에 했습니다: s, 두가지문발습니다생했제가:s다니.
set()시이꽤 걸니리서그, 래간서▁an▁takes.set(set())돌아올 것입니다set()빈 설정 테이블이 비어 있기 때문입니다(허허, 내 생각엔 :)- , 한세를얻위해기트,,
set({set()})그리고.set.add(set)때문에 작동하지 않을 것입니다.set()가능하지
두 가지 문제를 모두 해결하기 위해, 저는 사용했습니다.frozenset()그 말은 내가 원하는 것을 제대로 얻지 못한다는 것을 의미합니다(유형은 문자 그대로입니다).set), ), 를 set인터체인지 아닌지
def powerset(original_set):
# below gives us a set with one empty set in it
ps = set({frozenset()})
for member in original_set:
subset = set()
for m in ps:
# to be added into subset, needs to be
# frozenset.union(set) so it's hashable
subset.add(m.union(set([member]))
ps = ps.union(subset)
return ps
아래에는 2²(16)가 표시됩니다.frozenset출력만큼 정확합니다.
In [1]: powerset(set([1,2,3,4]))
Out[2]:
{frozenset(),
frozenset({3, 4}),
frozenset({2}),
frozenset({1, 4}),
frozenset({3}),
frozenset({2, 3}),
frozenset({2, 3, 4}),
frozenset({1, 2}),
frozenset({2, 4}),
frozenset({1}),
frozenset({1, 2, 4}),
frozenset({1, 3}),
frozenset({1, 2, 3}),
frozenset({4}),
frozenset({1, 3, 4}),
frozenset({1, 2, 3, 4})}
할 수 있는 방법이 없기 때문에.setset에서, 이 이러한 s 썬에서이돌을 , 만당신것을리싶다면고들약이이파▁s.frozenset에 끼워 넣다.sets, 당신은 그것들을 다시 지도로 만들어야 할 것입니다.list(list(map(set, powerset(set([1,2,3,4])))) 위의 또는 위의 내용을 수정합니다.
질문이 오래된 것일 수도 있지만, 제 코드가 누군가에게 도움이 되기를 바랍니다.
def powSet(set):
if len(set) == 0:
return [[]]
return addtoAll(set[0],powSet(set[1:])) + powSet(set[1:])
def addtoAll(e, set):
for c in set:
c.append(e)
return set
모든 하위 집합을 재귀와 함께 가져옵니다.미친놈 원라이너
from typing import List
def subsets(xs: list) -> List[list]:
return subsets(xs[1:]) + [x + [xs[0]] for x in subsets(xs[1:])] if xs else [[]]
Haskell 솔루션 기반
subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs
def findsubsets(s, n):
return list(itertools.combinations(s, n))
def allsubsets(s) :
a = []
for x in range(1,len(s)+1):
a.append(map(set,findsubsets(s,x)))
return a
이는 실제 Python 세트의 반환을 실제로 제공하는 답변이 없기 때문에 터무니없는 것입니다.다음은 실제로 Python인 파워셋을 제공하는 지저분한 구현입니다.set.
test_set = set(['yo', 'whatup', 'money'])
def powerset( base_set ):
""" modified from pydoc's itertools recipe shown above"""
from itertools import chain, combinations
base_list = list( base_set )
combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ]
powerset = set([])
for ll in combo_list:
list_of_frozensets = list( map( frozenset, map( list, ll ) ) )
set_of_frozensets = set( list_of_frozensets )
powerset = powerset.union( set_of_frozensets )
return powerset
print powerset( test_set )
# >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']),
# frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']),
# frozenset(['money','yo']), frozenset(['money']), frozenset([]) ])
하지만 저는 더 나은 구현을 보고 싶습니다.
다음은 조합을 사용하지만 기본 제공 기능만 사용하는 빠른 구현입니다.
def powerSet(array):
length = str(len(array))
formatter = '{:0' + length + 'b}'
combinations = []
for i in xrange(2**int(length)):
combinations.append(formatter.format(i))
sets = set()
currentSet = []
for combo in combinations:
for i,val in enumerate(combo):
if val=='1':
currentSet.append(array[i])
sets.add(tuple(sorted(currentSet)))
currentSet = []
return sets
범위 n의 모든 부분 집합이 집합으로 지정됩니다.
n = int(input())
l = [i for i in range (1, n + 1)]
for number in range(2 ** n) :
binary = bin(number)[: 1 : -1]
subset = [l[i] for i in range(len(binary)) if binary[i] == "1"]
print(set(sorted(subset)) if number > 0 else "{}")
import math
def printPowerSet(set,set_size):
pow_set_size =int(math.pow(2, set_size))
for counter in range(pow_set_size):
for j in range(set_size):
if((counter & (1 << j)) > 0):
print(set[j], end = "")
print("")
set = ['a', 'b', 'c']
printPowerSet(set,3)
이 질문의 변형은 "컴퓨터 과학의 발견:학제간 문제, 원칙 및 파이썬 프로그래밍. 2015년판".이 연습 10.2.11에서 입력은 정수이고 출력은 멱집합이어야 합니다.여기 나의 재귀적인 해결책이 있습니다(기본 파이썬3 외에는 다른 것을 사용하지 않습니다).
def powerSetR(n):
assert n >= 0
if n == 0:
return [[]]
else:
input_set = list(range(1, n+1)) # [1,2,...n]
main_subset = [ ]
for small_subset in powerSetR(n-1):
main_subset += [small_subset]
main_subset += [ [input_set[-1]] + small_subset]
return main_subset
superset = powerSetR(4)
print(superset)
print("Number of sublists:", len(superset))
그리고 그 출력은.
[[4], [3], [4, 3], [4, 2], [3, 2], [3, 2], [4, 3, 2], [1], [4, 1, 3, 1], [2, 1], [4, 2, 1], [3, 2, 1] 하위 목록의 수: 16개
나는 그를 보지 못했습니다.more_itertools.powerset기능을 사용할 것을 권장합니다.또한 출력의 기본 순서를 사용하지 않는 것이 좋습니다.itertools.combinations대신 위치 사이의 거리를 최소화하고 간격이 짧은 항목의 부분 집합을 간격이 큰 항목 위/앞에 정렬하려는 경우가 많습니다.
레시피 페이지에는 다음이 표시됩니다.chain.from_iterable
- 로 고는 다음과 .
r여기서 이항 계수의 하위 부분에 대한 표준 표기법과 일치합니다.s일반적으로 다음과 같이 언급됩니다.n및에 대해 "n Choiceer" ("n Choiceer")에서
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
여기에 있는 다른 예는 다음과 같은 검정력 집합을 제공합니다.[1,2,3,4]2-튜플이 "사전" 순서로 나열되는 방식(숫자를 정수로 인쇄할 때).숫자 사이의 거리(즉, 차이)를 옆에 쓰면 다음과 같은 점을 알 수 있습니다.
12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1
부분 집합에 대한 올바른 순서는 다음과 같이 최소 거리를 먼저 '배기'하는 순서여야 합니다.
12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3
하면 이 가 ' 것처럼 , 여서숫잘사자이 '된못이 '럼지기 '만이 '보문 ', 문를예 '있수 ', 들자로 '습다 ', 니를 '면처하 ' 등의 해 보세요.["a","b","c","d"]이것이 다음 순서로 전력 집합을 얻는 데 유용한 이유는 더 명확합니다.
ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3
이 효과는 항목이 많을수록 더욱 두드러지며, 나의 경우에는 파워 세트의 인덱스 범위를 의미 있게 설명할 수 있는 것과 차이가 있습니다.
(조합학에서 알고리즘의 출력 순서에 대해서는 회색 코드 등에 많이 적혀 있는데, 부수적인 문제로 보지는 않습니다.)
사실 저는 이 빠른 정수 파티션 코드를 사용하여 적절한 순서로 값을 출력하는 상당히 복잡한 프로그램을 작성했지만, 그 후에 저는 발견했습니다.more_itertools.powerset대부분의 용도에서 다음과 같은 기능을 사용해도 괜찮을 것입니다.
from more_itertools import powerset
from numpy import ediff1d
def ps_sorter(tup):
l = len(tup)
d = ediff1d(tup).tolist()
return l, d
ps = powerset([1,2,3,4])
ps = sorted(ps, key=ps_sorter)
for x in ps:
print(x)
⇣
()
(1,)
(2,)
(3,)
(4,)
(1, 2)
(2, 3)
(3, 4)
(1, 3)
(2, 4)
(1, 4)
(1, 2, 3)
(2, 3, 4)
(1, 2, 4)
(1, 3, 4)
(1, 2, 3, 4)
파워 세트를 멋지게 인쇄할 수 있는 관련 코드를 몇 개 더 작성했습니다(여기에 포함되지 않은 예쁜 인쇄 기능은 레포를 참조하십시오).print_partitions,print_partitions_by_length,그리고.pprint_tuple).
- Repo: 순서가 지정된 검정력 집합, 구체적으로
이 방법은 매우 간단하지만 다양한 수준의 전원 집합에 바로 액세스할 수 있는 코드가 필요한 경우에도 유용할 수 있습니다.
from itertools import permutations as permute
from numpy import cumsum
# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning#comment25080713_10036764
def asc_int_partitions(n):
a = [0 for i in range(n + 1)]
k = 1
y = n - 1
while k != 0:
x = a[k - 1] + 1
k -= 1
while 2 * x <= y:
a[k] = x
y -= x
k += 1
l = k + 1
while x <= y:
a[k] = x
a[l] = y
yield tuple(a[:k + 2])
x += 1
y -= 1
a[k] = x + y
y = x + y - 1
yield tuple(a[:k + 1])
# https://stackoverflow.com/a/6285330/2668831
def uniquely_permute(iterable, enforce_sort=False, r=None):
previous = tuple()
if enforce_sort: # potential waste of effort (default: False)
iterable = sorted(iterable)
for p in permute(iterable, r):
if p > previous:
previous = p
yield p
def sum_min(p):
return sum(p), min(p)
def partitions_by_length(max_n, sorting=True, permuting=False):
partition_dict = {0: ()}
for n in range(1,max_n+1):
partition_dict.setdefault(n, [])
partitions = list(asc_int_partitions(n))
for p in partitions:
if permuting:
perms = uniquely_permute(p)
for perm in perms:
partition_dict.get(len(p)).append(perm)
else:
partition_dict.get(len(p)).append(p)
if not sorting:
return partition_dict
for k in partition_dict:
partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
return partition_dict
def print_partitions_by_length(max_n, sorting=True, permuting=True):
partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
for k in partition_dict:
if k == 0:
print(tuple(partition_dict.get(k)), end="")
for p in partition_dict.get(k):
print(pprint_tuple(p), end=" ")
print()
return
def generate_powerset(items, subset_handler=tuple, verbose=False):
"""
Generate the powerset of an iterable `items`.
Handling of the elements of the iterable is by whichever function is passed as
`subset_handler`, which must be able to handle the `None` value for the
empty set. The function `string_handler` will join the elements of the subset
with the empty string (useful when `items` is an iterable of `str` variables).
"""
ps = {0: [subset_handler()]}
n = len(items)
p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
for p_len, parts in p_dict.items():
ps.setdefault(p_len, [])
if p_len == 0:
# singletons
for offset in range(n):
subset = subset_handler([items[offset]])
if verbose:
if offset > 0:
print(end=" ")
if offset == n - 1:
print(subset, end="\n")
else:
print(subset, end=",")
ps.get(p_len).append(subset)
for pcount, partition in enumerate(parts):
distance = sum(partition)
indices = (cumsum(partition)).tolist()
for offset in range(n - distance):
subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
if verbose:
if offset > 0:
print(end=" ")
if offset == n - distance - 1:
print(subset, end="\n")
else:
print(subset, end=",")
ps.get(p_len).append(subset)
if verbose and p_len < n-1:
print()
return ps
예를 들어 문자열을 명령줄 인수로 사용하는 CLI 데모 프로그램을 작성했습니다.
python string_powerset.py abcdef
⇣
a, b, c, d, e, f
ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af
abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf
abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef
abcde, bcdef
abcdf
abcef
abdef
acdef
abcdef
여기 제 솔루션이 있습니다. lmiguelvargasf의 솔루션과 (개념적으로) 유사합니다.
정의상 -[수학 항목] 파워 세트에는 빈 세트 -[개인 취향]가 포함되어 있으며 저는 냉동 세트를 사용하는 것을 좋아하지 않습니다.
따라서 입력은 목록이고 출력은 목록입니다.기능이 더 일찍 종료될 수도 있지만, 저는 파워 세트의 요소가 사전 편찬적으로 정렬되는 것을 좋아합니다. 그것은 본질적으로 좋은 의미입니다.
def power_set(L):
"""
L is a list.
The function returns the power set, but as a list of lists.
"""
cardinality=len(L)
n=2 ** cardinality
powerset = []
for i in range(n):
a=bin(i)[2:]
subset=[]
for j in range(len(a)):
if a[-j-1]=='1':
subset.append(L[j])
powerset.append(subset)
#the function could stop here closing with
#return powerset
powerset_orderred=[]
for k in range(cardinality+1):
for w in powerset:
if len(w)==k:
powerset_orderred.append(w)
return powerset_orderred
언급URL : https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset
'programing' 카테고리의 다른 글
| '스위프' 기능 사용 방법 (0) | 2023.06.13 |
|---|---|
| 닷넷의 프로세스 ID를 확인하는 동안 오류가 발생했습니다.응용 프로그램을 호스팅하는 exe.하나 이상의 오류가 발생했습니다. (0) | 2023.06.13 |
| ORA-06508: PL/SQL: 호출 중인 프로그램 단위를 찾을 수 없습니다. (0) | 2023.06.13 |
| 스위치 대/소문자 구분 기호를 사용하는 경우 'break' 문 (0) | 2023.06.13 |
| VueJS - 저장된 데이터의 반응성 제한 (0) | 2023.06.13 |