Python实现求一个集合所有子集的示例

时间:2022-10-27 15:17:12

方法一:回归实现

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def PowerSetsRecursive(items):
  """Use recursive call to return all subsets of items, include empty set"""
  
  if len(items) == 0:
    #if the lsit is empty, return the empty list
    return [[]]
  
  subsets = []
  first_elt = items[0] #first element
  rest_list = items[1:]
  
  #Strategy:Get all subsets of rest_list; for each of those subsets, a full subset list
  #will contain both the original subset as well as a version of the sebset that contains the first_elt
  
  for partial_sebset in PowerSetsRecursive(rest_list):
    subsets.append(partial_sebset)
    next_subset = partial_sebset[:] +[first_elt]
    subsets.append(next_subset)
  return subsets
?
1
2
3
4
5
6
def PowerSetsRecursive2(items):
  # the power set of the empty set has one element, the empty set
  result = [[]]
  for x in items:
    result.extend([subset + [x] for subset in result])
  return result

方法二:二进制法

?
1
2
3
4
5
6
7
8
9
10
11
def PowerSetsBinary(items):
  #generate all combination of N items
  N = len(items)
  #enumerate the 2**N possible combinations
  for i in range(2**N):
    combo = []
    for j in range(N):
      #test jth bit of integer i
      if(i >> j ) % 2 == 1:
        combo.append(items[j])
    yield combo

以上这篇Python实现求一个集合所有子集的示例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/tszw1007/article/details/77871133