没有重复和空箱的垃圾箱蛮力包装 [英] Bin packing bruteforce without duplicates and empty bins
问题描述
我想找到所有方法将 n
元素分发到 b
箱,但没有重复"和空箱.
示例
如果我有 n = 3
个元素和 b = 2
个 bin 并应用此 stackoverflow 线程中的蛮力方法 装箱蛮力方法我得到这些结果:
[[0, 1, 2, 3], []][[0, 1, 2], [3]][[0, 1, 3], [2]][[0, 1], [2, 3]][[0, 2, 3], [1]][[0, 2], [1, 3]][[0, 3], [1, 2]][[0], [1, 2, 3]][[1, 2, 3], [0]][[1, 2], [0, 3]][[1, 3], [0, 2]][[1], [0, 2, 3]][[2, 3], [0, 1]][[2], [0, 1, 3]][[3], [0, 1, 2]][[], [0, 1, 2, 3]]
重复"的定义
一半的结果是重复的.仅切换 bin 的顺序:第一个和最后一个相同,第 2 个和第 2 个到最后一个相同,依此类推...
空箱的定义
我不希望任何垃圾箱是空的.如果你看前面的例子,第一行和最后一行都有一个空箱.
这种分区的数量称为第二类斯特林数.关于这些数字的 维基百科文章给出了一个递推关系,可以修改该递推关系以给出递归函数来生成这些分区.以下 Python 实现使用 memoization 来保持计算可行:
def add(a,p,i):#将a添加到分区p的第i个单元格#返回一个新的分区返回 [piece + [a] if j == i else piece for j,piece in enumerate(p)]def addToAll(a,p):#将a添加到p的所有部分#返回分区列表返回 [add(a,p,i) for i in range(len(p))]定义分区(n,k):memoDict = {}def helperPart(n,k):如果 n == 0 且 k == 0:返回 [[]]elif n == 0 或 k == 0:返回 []memoDict 中的 elif (n,k):返回 memoDict[(n,k)]别的:kParts = helperPart(n-1,k)kMinusParts = helperPart(n-1,k-1)零件 = [零件 + [[n]] 用于 kMinusParts 中的零件]对于 kParts 中的 p:部分.extend(addToAll(n,p))memoDict[(n,k)] = 部分退回零件返回 helperPart(n,k)
例如:
<预><代码>>>>分区 = 分区(5,3)>>>对于分区中的 p:print(p)[[1, 2, 3], [4], [5]][[1, 2, 4], [3], [5]][[1, 2], [3, 4], [5]][[1, 3, 4], [2], [5]][[1, 3], [2, 4], [5]][[1, 4], [2, 3], [5]][[1], [2, 3, 4], [5]][[1, 2, 5], [3], [4]][[1, 2], [3, 5], [4]][[1, 2], [3], [4, 5]][[1, 3, 5], [2], [4]][[1, 3], [2, 5], [4]][[1, 3], [2], [4, 5]][[1, 5], [2, 3], [4]][[1], [2, 3, 5], [4]][[1], [2, 3], [4, 5]][[1, 4, 5], [2], [3]][[1, 4], [2, 5], [3]][[1, 4], [2], [3, 5]][[1, 5], [2, 4], [3]][[1], [2, 4, 5], [3]][[1], [2, 4], [3, 5]][[1, 5], [2], [3, 4]][[1], [2, 5], [3, 4]][[1], [2], [3, 4, 5]]效率相当高:将 10 个对象的 42,525 个分区生成到 5 个 bin 中所需的时间不到一秒.
I want to find all ways to distribute n
elements to b
bins but without "duplicates" and empty bins.
Example
If I have n = 3
elements and b = 2
bins and apply the bruteforce method from this stackoverflow thread Bin packing bruteforce method I get these results:
[[0, 1, 2, 3], []]
[[0, 1, 2], [3]]
[[0, 1, 3], [2]]
[[0, 1], [2, 3]]
[[0, 2, 3], [1]]
[[0, 2], [1, 3]]
[[0, 3], [1, 2]]
[[0], [1, 2, 3]]
[[1, 2, 3], [0]]
[[1, 2], [0, 3]]
[[1, 3], [0, 2]]
[[1], [0, 2, 3]]
[[2, 3], [0, 1]]
[[2], [0, 1, 3]]
[[3], [0, 1, 2]]
[[], [0, 1, 2, 3]]
Definition of "duplicates"
Half of the results are duplicates. Only the order of the bins is switched: First and last is the same, 2nd and 2nd to last is the same, etc...
Definition of empty bins
I don't want any bins to be empty. If you look at the previous example the first and the last line have an empty bin.
The number of such partitions is called a Stirling number of the second kind. The Wikipedia article on these numbers gives a recurrence relation which can be modified to give a recursive function for generating these partitions. The following Python implementation uses memoization to keep the computation feasible:
def add(a,p,i):
#adds a to the ith cell of partition p
#returns a new partiton
return [piece + [a] if j == i else piece for j, piece in enumerate(p)]
def addToAll(a,p):
#adds a to all pieces of p
#returns a list of partitions
return [add(a,p,i) for i in range(len(p))]
def partition(n,k):
memoDict = {}
def helperPart(n,k):
if n == 0 and k == 0: return [[]]
elif n == 0 or k == 0: return []
elif (n,k) in memoDict:
return memoDict[(n,k)]
else:
kParts = helperPart(n-1,k)
kMinusParts = helperPart(n-1,k-1)
parts = [part + [[n]] for part in kMinusParts]
for p in kParts:
parts.extend(addToAll(n,p))
memoDict[(n,k)] = parts
return parts
return helperPart(n,k)
For example:
>>> partitions = partition(5,3)
>>> for p in partitions: print(p)
[[1, 2, 3], [4], [5]]
[[1, 2, 4], [3], [5]]
[[1, 2], [3, 4], [5]]
[[1, 3, 4], [2], [5]]
[[1, 3], [2, 4], [5]]
[[1, 4], [2, 3], [5]]
[[1], [2, 3, 4], [5]]
[[1, 2, 5], [3], [4]]
[[1, 2], [3, 5], [4]]
[[1, 2], [3], [4, 5]]
[[1, 3, 5], [2], [4]]
[[1, 3], [2, 5], [4]]
[[1, 3], [2], [4, 5]]
[[1, 5], [2, 3], [4]]
[[1], [2, 3, 5], [4]]
[[1], [2, 3], [4, 5]]
[[1, 4, 5], [2], [3]]
[[1, 4], [2, 5], [3]]
[[1, 4], [2], [3, 5]]
[[1, 5], [2, 4], [3]]
[[1], [2, 4, 5], [3]]
[[1], [2, 4], [3, 5]]
[[1, 5], [2], [3, 4]]
[[1], [2, 5], [3, 4]]
[[1], [2], [3, 4, 5]]
It is reasonably efficient: it takes less than a second to generate the 42,525 partitions of 10 objects into 5 bins.
这篇关于没有重复和空箱的垃圾箱蛮力包装的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!