집합의 모든 하위 집합을 얻는 방법은 무엇입니까?

집합의 모든 하위 집합을 얻는 방법은 무엇입니까? (파워 셋)

---

주어진 세트

{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 itertools페이지 에는 정확히 이에 대한 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')]

처음에 빈 튜플이 마음에 들지 않으면 0 길이 조합을 피하기 위해 range문을 range(1, len(s)+1)로 변경할 수 있습니다 .

---

다음은 powerset에 대한 추가 코드입니다. 이것은 처음부터 작성되었습니다.

>>> 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]

Mark Rushakoff의 주석은 여기에 적용 할 수 있습니다. "처음에 빈 튜플이 마음에 들지 않으면 on."범위 문을 range (1, len (s) +1)로 변경하여 길이가 0 인 조합을 피할 수 있습니다. "내 경우를 제외하고는 변경 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은 단일 메모리에서 모든 결과를 계산할 필요가 없음을 의미합니다. 메인 루프 외부에서 마스크를 미리 계산하는 것은 가치있는 최적화라고 가정합니다.

---

빠른 답변을 찾고 있다면 Google에서 "python power set"을 검색하여 다음을 찾았습니다. 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은 원하는 모든 요소의 목록이며 정렬 및 인쇄 할 수 있습니다.

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]]

---

def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])

---

powerset의 개선이 있습니다.

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

---

다음 알고리즘은 매우 명확하고 간단합니다.

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_all_subsets(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

powerset을 생성 할 수있는 또 다른 방법은 n비트 가있는 모든 이진수를 생성하는 것 입니다. 파워 세트로 n숫자가 있는 숫자 의 양은입니다 2 ^ n. 이 알고리즘의 원리는 이진 숫자가 하나 또는 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 컴퓨터 사고 및 데이터 과학에 대한 소개를받을 때 두 가지 알고리즘을 모두 찾았으며 이것이 제가 본 것을 이해하기 가장 쉬운 알고리즘 중 하나라고 생각합니다.

---

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
      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]]

---

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- 문자열을 사용이 가능하도록. 기본적으로이를 통해 각 반복 중에 각 하위 집합에 추가 할 요소를 선택할 수 있습니다. 입력 세트에 3 개의 요소가 있다고 가정 해 보겠습니다 {0, 1, 2}. 따라서 선택자는 0에서 7 (포함) 사이의 값을 가져 오며 이진법은 다음과 같습니다.

000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7

따라서 각 비트는 원래 세트의 요소를 추가해야하는지 여부를 표시기 역할을 할 수 있습니다. 이진수를보고 각 숫자를 상위 집합 1의 요소로 생각하면 인덱스에있는 요소 j가 추가 0되어야하며이 요소가 추가되지 않아야 함을 의미합니다.

집합 이해력을 사용하여 각 반복에서 하위 집합을 생성하고이 하위 집합을로 변환 frozenset하여 ps(파워 집합)에 추가 할 수 있습니다 . 그렇지 않으면 Python의 집합이 변경 불가능한 객체로만 구성되기 때문에 추가 할 수 없습니다.

단순화

일부 파이썬 이해를 사용하여 코드를 단순화 할 수 있으므로 for 루프를 제거 할 수 있습니다. 인덱스 사용 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예상대로 작동하더라도 의존하는 것이 매우 마술처럼 보이기 때문에 다른 알고리즘보다 더 명확하고 직관적이라는 것 입니다.

---

빠른 파워 세트 리프레셔!

집합 X의 거듭 제곱 집합은 단순히 빈 집합을 포함하여 X의 모든 하위 집합 집합입니다.

예제 세트 X = (a, b, c)

파워 세트 = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {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

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')]

자세한 내용 은 itertools 문서 , 전원 세트 에 대한 wikipedia 항목을 참조하십시오.

---

이 답변의 거의 대부분은 나에게 약간의 속임수처럼 느껴지는 list대신 사용 set합니다. 그래서 호기심으로 저는 set다른 "파이썬을 처음 접하는"사람들을 위해 진정으로 간단한 버전을 만들고 요약 하려고했습니다 .

나는 파이썬의 세트 구현 을 다루는 데 몇 가지 이상한 점이 있음을 발견했습니다 . 나에게 가장 놀라운 것은 빈 세트를 다루는 것이 었습니다. 이것은 Ruby의 Set 구현 과는 대조적입니다 . 여기서는 단순히 빈 하나를 포함 Set[Set[]]하여 얻을 수 있으므로 처음에는 약간 혼란 스러웠습니다.SetSet

검토하기 위해 s 를 사용하는 powerset동안 set두 가지 문제가 발생했습니다.

1. set()iterable을 취 하므로 빈 세트 iterable이 비어 있기 때문에set(set()) 반환됩니다 (duh 내가 생각합니다 :))set()
2. 세트의 세트를 얻기 위해, 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) frozensets를 출력으로 올바르게 얻습니다 .

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})}

파이썬에서는 setof sets 를 가질 수있는 방법이 없기 때문에 ,이 frozensets를 sets 로 바꾸려면 다시 list( list(map(set, powerset(set([1,2,3,4])))) ) 로 매핑 하거나 위를 수정해야합니다.

---

이 답변 중 실제로 실제 Python 세트의 반환을 제공하지 않기 때문에 이것은 야생입니다. 실제로 Python 인 powerset을 제공하는 지저분한 구현이 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

---

A simple way would be to harness the internal representation of integers under 2's complement arithmetic.

Binary representation of integers is as {000, 001, 010, 011, 100, 101, 110, 111} for numbers ranging from 0 to 7. For an integer counter value, considering 1 as inclusion of corresponding element in collection and '0' as exclusion we can generate subsets based on the counting sequence. Numbers have to be generated from 0 to pow(2,n) -1 where n is the length of array i.e. number of bits in binary representation.

A simple Subset Generator Function based on it can be written as below. It basically relies

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

and then it can be used as

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

Testing

Adding following in local file

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

gives following output

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']]

---

In Python 3.5 or greater, you can use the yield from statement along with itertools.combinations:

def subsets(iterable):
    for n in range(len(iterable)):
        yield from combinations(iterable, n + 1)

---

With empty set, which is part of all the subsets, you could use:

def subsets(iterable):
    for n in range(len(iterable) + 1):
        yield from combinations(iterable, n)

---

Perhaps the question is getting old, but I hope my code will help someone.

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

참고URL : https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset