[PYTHON] 세트의 모든 부분 집합을 얻는 방법? (powerset)

세트의 모든 부분 집합을 얻는 방법? (powerset)

주어진 집합

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

해결법

1. ==============================

   1.파이썬 itertools 페이지에는 이것을위한 powerset 레시피가 정확히있다.

   파이썬 itertools 페이지에는 이것을위한 powerset 레시피가 정확히있다.

   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 인 조합을 피할 수 있습니다.

2. ==============================

   2.다음은 powerset에 대한 더 많은 코드입니다. 이것은 처음부터 쓰여졌습니다 :

   다음은 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의 코멘트는 여기에 적용됩니다 : "시작 부분에 빈 튜플이 마음에 들지 않으면 range 문을 range (1, len (s) +1)로 변경하면 길이가 0 인 조합을 피할 수 있습니다 ", 제 경우를 제외하고 범위 (1 << x)에서 범위 (1, 1 << x)의 i에 대해 i를 변경합니다.

   몇 년 후로 돌아가서 이제 다음과 같이 작성했습니다.

   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를 사용하면 단일 결과로 모든 결과를 계산할 필요가 없습니다. 메인 루프 외부의 마스크를 미리 계산하는 것은 가치있는 최적화라고 가정합니다.

3. ==============================

   3.빠른 답변을 원한다면 Google에서 "python power set"을 검색하여 다음과 같이 생각해 냈습니다. Python Power Set Generator

   빠른 답변을 원한다면 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]]
   

4. ==============================

   4.

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

5. ==============================

   5.powerset의 세련미가 있습니다.

   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
   

6. ==============================

   6.

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

7. ==============================

   7.필자는 가장 이해하기 쉬운 솔루션 인 안티 코드 골프 버전을 제공하기를 원했습니다.

   필자는 가장 이해하기 쉬운 솔루션 인 안티 코드 골프 버전을 제공하기를 원했습니다.

   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 항목도 전원 세트에 있습니다.

8. ==============================

   8.이 대답들 중 어느 것도 실제로 파이썬 세트를 반환하지 않기 때문에 이것은 매우 어려움을 가지고 있습니다. 실제로 파이썬 세트 인 powerset을 제공하는 지저분한 구현입니다.

   이 대답들 중 어느 것도 실제로 파이썬 세트를 반환하지 않기 때문에 이것은 매우 어려움을 가지고 있습니다. 실제로 파이썬 세트 인 powerset을 제공하는 지저분한 구현입니다.

   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([]) ])
   

   그래도 더 나은 구현을보고 싶습니다.

9. ==============================

   9.다음은 조합을 사용하지만 내장 기능 만 사용하는 빠른 구현입니다.

   다음은 조합을 사용하지만 내장 기능 만 사용하는 빠른 구현입니다.

   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
   

10. ==============================

    10.나는 다음과 같은 알고리즘을 매우 명확하고 간단하게 발견했다.

    나는 다음과 같은 알고리즘을 매우 명확하고 간단하게 발견했다.

    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 비트를 갖는 모든 2 진수를 생성하는 것입니다. 전력 설정으로 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 전산 사고 및 데이터 과학 개론 (Introduction to Computing Thinking and Data Science)을 보았을 때 두 알고리즘을 모두 발견했으며, 내가 본 것을 이해하는 가장 쉬운 알고리즘 중 하나라고 생각합니다.

from https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset by cc-by-sa and MIT license