在Python中将集合分成k组（包括空集）。

Question

有一些类似于这篇文章的帖子 我有一个数字列表，如何生成所有唯一的k分区?

但我想知道是否有一些新的高效库来解决这个问题（itertools? sagemath?）

我有一个数字列表，如何生成所有唯一有序的k分区？ 例如，如果我有[1,2,3,4,5]和k=3

[[1,2],[3],[4,5]]是这样的一个分区 但[[4,5],[3],[1,2]]也是这样的一个分区

我还想将NULL集作为可能的集合之一包含在k子集中

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

顺序在以下情况下很重要：

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

并且 [[4,5],[3],[1,2]]

但是如果您跟着我，[[2,1],[3],[5,4]] 被认为与 [[1,2],[3],[4,5]] 相同...

据我所知，从Sagemath获取OrderedSetPartitions(5,3)不能提供我问题的答案，因为它排除了空集

编辑：这里是使用SAGEMATH天真地解决此问题的（未经优化的）尝试

def OrderedSetPartitions_0(A,k):

    cols={i for i in range(k)}
    # returns the list of k-OrderedSetPartitions of A, allowing for the empty set
    s=Subsets(cols).list()
    res=[]
    count=0
    P=[OrderedSetPartitions(A,i) for i in range(k+1)]

    for sub in s:
           print("sub=")
           print(sub)

           tmp=[ {} for i in range(k)]
           c=sub.cardinality()
           for part in P[c]:
               print("part=")
               print(part)
               for i in range(c):
                   tmp[sub[i]]=part[i]

               print("tmp=")
               print(tmp)

               res=res.append([tmp])
               # res = res.append(tmp) # tried this too
               print("res=")
               print(res)
               count=count+1
    return(res)
    # print(count)

A=range(3)
k=2
A
P=[OrderedSetPartitions(A,i) for i in range(k+1)]
# note that P[2].list is a list of list !
P[2].list()

[[{0, 1}, {2}],
 [{0, 2}, {1}],
 [{1, 2}, {0}],
 [{0}, {1, 2}],
 [{1}, {0, 2}],
 [{2}, {0, 1}]]

myset=OrderedSetPartitions_0(A,k)

我收到了这个错误信息，我承认我完全不理解，因为在编码时看起来一切正常，但是不知何故res似乎是“None”，而不是[]。

sub=
{}
sub=
{0}
part=
[{0, 1, 2}]
tmp=
[{0, 1, 2}, {}]
res=
None
sub=
{1}
part=
[{0, 1, 2}]
tmp=
[{}, {0, 1, 2}]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_21.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("#

-- coding: utf-8 --\n" + support.preparse_worksheet_cell(base64.b64decode("bXlzZXQ9T3JkZXJlZFNldFBhcnRpdGlvbnNfMChBLGsp"),globals())+"\n"); execfile(os.path.abspath("code.py")) File "", line 1, in

  File "/private/var/folders/gm/z065gk616xg6g0xgn4c7_bvc0000gn/T/tmpryfYOj/___code___.py", line 2, in <module>
    exec compile(u'myset=OrderedSetPartitions_0(A,k)
  File "", line 1, in <module>

  File "/private/var/folders/gm/z065gk616xg6g0xgn4c7_bvc0000gn/T/tmpSH_9LF/___code___.py", line 27, in OrderedSetPartitions_0
    res=res.append([tmp])
AttributeError: 'NoneType' object has no attribute 'append'

问题是关于将列表聚合成res。如果我在涉及到res的所有行上放置一个井号，我可以正确地枚举输出。

编辑： 感谢您的回答。 实际上，我将res=res.append（tmp）更改为res.append（tmp） 当执行print（tmp）时，我得到了正确的枚举。

[{0, 1, 2}, {}, {}] [{}, {0, 1, 2}, {}] [{}, {}, {0, 1, 2}] [{0, 1}, {2}, {}] [{0, 2}, {1}, {}] [{1, 2}, {0}, {}] [{0}, {1, 2}, {}] [{1}, {0, 2}, {}] [{2}, {0, 1}, {}] [{0, 1}, {}, {2}] [{0, 2}, {}, {1}] [{1, 2}, {}, {0}] [{0}, {}, {1, 2}] [{1}, {}, {0, 2}] [{2}, {}, {0, 1}] [{}, {0, 1}, {2}] [{}, {0, 2}, {1}] [{}, {1, 2}, {0}] [{}, {0}, {1, 2}] [{}, {1}, {0, 2}] [{}, {2}, {0, 1}] [{0}, {1}, {2}] [{0}, {2}, {1}] [{1}, {0}, {2}] [{2}, {0}, {1}] [{1}, {2}, {0}] [{2}, {1}, {0}]

但是奇怪的是结果错误了，可能存在一些副作用。

[[{0, 1, 2}, {}, {}],
 [{}, {0, 1, 2}, {}],
 [{}, {}, {0, 1, 2}],
 [{2}, {0, 1}, {}],
 [{2}, {0, 1}, {}],
 [{2}, {0, 1}, {}],
 [{2}, {0, 1}, {}],
 [{2}, {0, 1}, {}],
 [{2}, {0, 1}, {}],
 [{2}, {}, {0, 1}],
 [{2}, {}, {0, 1}],
 [{2}, {}, {0, 1}],
 [{2}, {}, {0, 1}],
 [{2}, {}, {0, 1}],
 [{2}, {}, {0, 1}],
 [{}, {2}, {0, 1}],
 [{}, {2}, {0, 1}],
 [{}, {2}, {0, 1}],
 [{}, {2}, {0, 1}],
 [{}, {2}, {0, 1}],
 [{}, {2}, {0, 1}],
 [{2}, {1}, {0}],
 [{2}, {1}, {0}],
 [{2}, {1}, {0}],
 [{2}, {1}, {0}],
 [{2}, {1}, {0}],
 [{2}, {1}, {0}]]

前三行是正确的，然后它开始与我使用print（tmp）得到的结果不同。对我来说这很奇怪，因为在print(tmp)和res.append(tmp)之间没有任何指令！！！！

- Fagui Curtain

---

你看到的错误是由 res=res.append([tmp]) 引起的。列表方法 append 直接修改列表，不会返回一个值。因此，res 被赋值为 None 作为结果。只需删除该赋值即可（尽管我认为您的代码可能还有其他问题）。 - user3717023

还有两件事：当附加 tmp 时，你需要创建一个新的 tmp 副本，因为后续修改会影响你已经附加的内容。使用 res.append(tmp[:])。另外，{} 不是空集合，而是一个空字典。使用 set() 或 Set() 表示空集合。 - user3717023

非常感谢，这确实是我“错误”的原因... - Fagui Curtain

Answer 1

以下是使用Sagemath解决问题的方案，使用NumPy数组和itertools。其思路与您的代码相同：创建OrderedSetPartitions并加入空集以增强它们。为了避免过多循环，使用NumPy数组：关键部分是partitions[:, s] = P，其中2D数组partitions的某些列最初填充为空集，并被来自OrderedSetPartitions的非空集替换。

import numpy as np
from itertools import combinations
A = Set([1, 2, 3, 4, 5])        # Sage set, not Python set
k = 3                           # number of elements in partition
all_partitions = np.array(OrderedSetPartitions(A, k).list())
for i in range(k-1, 0, -1):
    P = np.array(OrderedSetPartitions(A, i).list()) if i > 1 else [[A]]
    for s in combinations(range(k), i):
        partitions = np.empty((len(P), k), dtype=object)
        partitions[:, :] = [[Set()]]
        partitions[:, s] = P
        all_partitions = np.vstack((all_partitions, partitions))
print all_partitions

输出是一个双重NumPy数组。如果需要Python列表，可以返回all_partitions.tolist()。

技术细节

Sage 集合（通过 Set([1,2,3]) 创建）和 Python 集合（通过 set([1,2,3]) 或 {1,2,3,4,5} 创建）是不同类的对象。在 Sagemath 中，Sage 集合的输出效果更好：它们显示为 {1, 2, 3}，而 Python 集合则显示为 set([1,2,3])。因此，在 Sagemath 中应优先选择 Sage 集合。此外，OrderedSetPartitions 返回 Sage 集合。

但是，要让 NumPy 和 Sage 集合一起工作需要付出更多的努力：特别地，我无法让 np.full 接受空的 Sage 集合 Set() 作为填充对象。这就是使用 np.empty 然后再进行填充的原因。

另一个类似的问题导致了 i == 1 的情况被不同对待：NumPy 尝试将 [[Set([1,2,3,4,5])]] 转换为一个三维数字数组，而不是包含一个 Sage 集合对象的二维数组。

- user3717023

---

谢谢您的回答。我已经进行了编辑。如果您能帮忙解决我的错误，我想知道原因。谢谢。 - Fagui Curtain