没有重复和空箱的垃圾箱蛮力包装 [英] 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屋！