在 Python 中将分区设置为 k 组(包括 NULL 集)
Set partitions into k groups (including the NULL set) in Python
有几个这样的帖子
I have a list of numbers, how to generate all unique k-partitions?
但我想知道是否有一些新的高效库可以解决这个问题 (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)
不会提供我的问题的答案,因为它排除了 NULL 集
编辑:这是一个(完全没有优化的)尝试使用 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}]
不过奇怪的是res错了,一定是有副作用的
[[{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}]]
前 3 行是正确的,然后它开始与我在 print(tmp)
中得到的不同。这对我来说很奇怪,因为 print(tmp)
和 res.append(tmp)
之间没有指令!!!!!
这是 Sagemath 中的解决方案,使用 NumPy 数组和 itertools。这个想法与您的代码中的相同:创建 OrderedSetPartitions 并用空集增强它们。为了在没有太多循环的情况下做到这一点,使用了 NumPy 数组:关键部分是 partitions[:, s] = P
,其中二维数组的某些列 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 列表,您可以 return all_partitions.tolist()
。
技术
贤者集(用Set([1,2,3])
创建)和Python集(用set([1,2,3])
或{1,2,3,4,5}
创建)是不同类的对象。在 Sagemath 中,Sage 集的输出看起来更好:它们显示为 {1,2,3},而 Python 集显示为 set([1,2,3])
。出于这个原因,Sage 集在 Sagemath 中是首选。此外,OrderedSetPartitions returns Sage 集。
但是让 NumPy 与 Sage 集一起玩需要更多的努力:特别是,我无法 np.full
接受空的 Sage 集 Set()
作为填充对象。这就是为什么要用np.empty
然后填进去的原因。
一个类似的问题导致案例 i == 1
被不同对待:NumPy 试图将 [[Set([1,2,3,4,5])]]
转换为三维数组而不是包含一个 Sage 集的二维数组目的。
有几个这样的帖子 I have a list of numbers, how to generate all unique k-partitions?
但我想知道是否有一些新的高效库可以解决这个问题 (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)
不会提供我的问题的答案,因为它排除了 NULL 集
编辑:这是一个(完全没有优化的)尝试使用 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}]
不过奇怪的是res错了,一定是有副作用的
[[{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}]]
前 3 行是正确的,然后它开始与我在 print(tmp)
中得到的不同。这对我来说很奇怪,因为 print(tmp)
和 res.append(tmp)
之间没有指令!!!!!
这是 Sagemath 中的解决方案,使用 NumPy 数组和 itertools。这个想法与您的代码中的相同:创建 OrderedSetPartitions 并用空集增强它们。为了在没有太多循环的情况下做到这一点,使用了 NumPy 数组:关键部分是 partitions[:, s] = P
,其中二维数组的某些列 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 列表,您可以 return all_partitions.tolist()
。
技术
贤者集(用Set([1,2,3])
创建)和Python集(用set([1,2,3])
或{1,2,3,4,5}
创建)是不同类的对象。在 Sagemath 中,Sage 集的输出看起来更好:它们显示为 {1,2,3},而 Python 集显示为 set([1,2,3])
。出于这个原因,Sage 集在 Sagemath 中是首选。此外,OrderedSetPartitions returns Sage 集。
但是让 NumPy 与 Sage 集一起玩需要更多的努力:特别是,我无法 np.full
接受空的 Sage 集 Set()
作为填充对象。这就是为什么要用np.empty
然后填进去的原因。
一个类似的问题导致案例 i == 1
被不同对待:NumPy 试图将 [[Set([1,2,3,4,5])]]
转换为三维数组而不是包含一个 Sage 集的二维数组目的。