如何找到A组的所有子集？在Python中设置分区

发布时间：2020-12-20 12:08:10 所属栏目：Python 来源：网络整理

导读：我想找到一个给出集合A的算法来查找满足以下条件的所有子集组： x ∪ y ∪ …. z = A,where x,y,… z ∈ Group 和 ? x,y ∈ Group: x ? A,y ? A,x ∩ y = ? = {} 和 ? x ∈ Group: x != ? 注意：我希望很好地定义它,我对数学符号不好我做了以下方法来搜索两

我想找到一个给出集合A的算法来查找满足以下条件的所有子集组：

x ∪ y ∪ …. z = A,where x,y,… z ∈ Group

和

? x,y ∈ Group: x ? A,y ? A,x ∩ y = ? = {}

和

? x ∈ Group: x != ?

注意：我希望很好地定义它,我对数学符号不好

我做了以下方法来搜索两个子集的组：

from itertools import product,combinations

def my_combos(A):
  subsets = []
  for i in xrange(1,len(A)):
    subsets.append(list(combinations(A,i)))
  combos = []
  for i in xrange(1,1+len(subsets)/2):
    combos.extend(list(product(subsets[i-1],subsets[-i])))
  if not len(A) % 2:
    combos.extend(list(combinations(subsets[len(A)/2-1],2)))
  return [combo for combo in combos if not set(combo[0]) & set(combo[1])]

my_combos({1,2,3,4})

我得到以下输出,这些都是由两个子集组成的组

[
  ((1,),(2,4)),((2,(1,((3,((4,3)),((1,2),(3,3),4),3))
]

…..但是,由一个,三个,四个子集组成的组….

题：

我怎么能找到一般解决方案？

例如以下预期输出：

my_combos({1,4})

[
  ((1,(4,)),))
]

解决方法

解：

def partitions(A):
    if not A:
        yield []
    else:
        a,*R = A
        for partition in partitions(R):
            yield partition + [[a]]
            for i,subset in enumerate(partition):
                yield partition[:i] + [subset + [a]] + partition[i+1:]

说明：

>空集只有空分区.
>对于非空集,取出一个元素,然后对剩余元素的每个分区,将该元素添加为其自己的子集,或将其添加到分区的子集之一.
>请注意,分区实际上是一组集合.我只将它表示为列表列表,因为它更快,因为我不想使用frozensets,它不能很好地打印.元组更快,问题要求他们,但我不能忍受单元素元组的逗号.

测试输出：

for partition in partitions({1,4}):
    print(partition)

[[4],[3],[2],[1]]
[[4,1],[2]]
[[4],[3,[2,1]]
[[4,2],[3]]
[[4,1]]
[[4],2]]
[[4],3],[2]]
[[4,1]]

输出速度测试(在相对较弱的笔记本电脑上)：

from time import time
print('elements partitions seconds')
for n in range(14):
    t0 = time()
    number = sum(1 for partition in partitions(range(n)))
    print('{:5}{:10}{:11.2f}'.format(n,number,time() - t0))

elements partitions seconds
    0         1       0.00
    1         1       0.00
    2         2       0.00
    3         5       0.00
    4        15       0.00
    5        52       0.00
    6       203       0.00
    7       877       0.00
    8      4140       0.06
    9     21147       0.07
   10    115975       0.36
   11    678570       2.20
   12   4213597      13.56
   13  27644437      87.59

我用OEIS page确认了那些分区号.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!