如何将 python 列表的所有子集分箱到 n 个分箱

Question

我有一个列表：

a = range(2)

并且我正在尝试以所有可能的方式将列表的内容分装到 n(=3) 个箱中，给出（顺序不重要）：

[[[],[0],[1]],
[[],[1],[0]],
[[],[0,1],[]],
[[],[],[0,1]],
[[0],[1],[]],
[[0],[],[1]],
[[1],[0],[]],
[[1],[],[0]],
[[0,1],[],[]]]

到目前为止，我一直在使用 sympy.utilities.iterables 库，首先获取所有可能的子集并过滤 variations 方法的输出以获得所需的结果：

def binner(a,n=3):
    import numpy as np
    import sympy.utilities.iterables as itt
    import itertools as it
    b = list(itt.subsets(a))    #get all subsets
    b.append(())                #append empty tuple to allow two empty bins
    c=list(itt.variations(b,n)) 
    d=[]
    for x in c:
        if np.sum(np.bincount(list(it.chain.from_iterable(x))))==len(a):
            d.append(x)     # add only combinations with no repeats and with all included
    return list(set(d))             # remove duplicates

我觉得有更好的方法可以做到这一点。有人可以帮忙吗？

请注意，我不受 sympy 库的约束，并且对任何基于 python/numpy 的替代方案持开放态度。

Answer 1

写一个递归函数来做这个怎么样？

基本思路是

subset(bins, l) 等于 [l]，因为您刚刚一箱放置值
subset(bins, l) = l[i] + subset(bins-1, lp) 其中 lp = l 无 l[i]

+

[l] + subset(bins-1, []) -> 全部放入一个箱子
+

[] + subset(bins, l) -> 将 none 放入 bin

因此 subset(3, [0, 1]) = [ [0] + subset(2, [1]) , [1] + subset(2, [0]) , [0, 1] , subset(2, []) , [] + subset(2, []) ]

代码如下

def subset(bins, l):
    if bins == 1:
        if l == []:
            return [[]]
        return [[l]]
    all_possible = []
    for i in range(len(l)): # choosing one element 
        a = l[:]
        x = l[i]
        a.pop(i)
        if len(a) > 0:
            y = subset(bins-1, a) # recurse for that list minus chosen one
            for j in y:
                all_possible.append([[x]] + j)
    y = subset(bins-1, l) # dont take out any element
    for j in y:
        all_possible.append([[]] + j)
    y = [[]] * (bins-1) # take out all elements
    all_possible.append([l] + y)
    return all_possible

输出 -

[[[0], [], [1]], [[0], [1], []], [[1], [], [0]], [[1], [0], []], [[], [0], [1]], [[], [1], [0]], [[], [], [0, 1]], [[], [0, 1], []], [[0, 1], [], []]]

Answer 2

假设我理解您的目标（不确定在重复元素的情况下您可能希望发生什么，即您是否要将它们视为不同的），您可以使用 itertools.product:

import itertools

def everywhere(seq, width):
    for locs in itertools.product(range(width), repeat=len(seq)):
        output = [[] for _ in range(width)]
        for elem, loc in zip(seq, locs):
            output[loc].append(elem)
        yield output

这给出了

>>> for x in everywhere(list(range(2)), 3):
...     print(x)
...     
[[0, 1], [], []]
[[0], [1], []]
[[0], [], [1]]
[[1], [0], []]
[[], [0, 1], []]
[[], [0], [1]]
[[1], [], [0]]
[[], [1], [0]]
[[], [], [0, 1]]

Answer 3

from itertools import permutations

a = range(2)


# get all the possible combinations

indexes = ','.join([str(i) for i in range(len(a))])+","
comb = []
perms = [''.join(p) for p in permutations(indexes)]
for x in perms:
    candidate = [[int(i) for i in  list(s)] if len(s) !=0 else [] for s in x.split(',') ]
    if candidate not in comb and [row[::-1] for row in candidate] not in comb:
        comb.append(candidate)

for item in comb:
    print item

>>
 [[0], [1], []]
 [[0], [], [1]]
 [[0, 1], [], []]
 [[], [0, 1], []]
 [[], [0], [1]]
 [[], [1], [0]]
 [[], [], [0, 1]]
 [[1], [0], []]
 [[1], [], [0]]

如何将 python 列表的所有子集分箱到 n 个分箱

How to bin all subsets of a python list into n bins

python

combinations

numpy

sympy

itertools