Bin packing bruteforce 没有重复和空箱

Question

我想找到所有方法将 n 元素分配到 b 个容器但没有 "duplicates" 和空容器。

例子

如果我有 n = 3 个元素和 b = 2 个容器并从这个 Whosebug 线程应用暴力破解方法 Bin packing bruteforce method 我得到这些结果：

[[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]]

"duplicates"

的定义

一半的结果是重复的。只是切换了 bin 的顺序：第一个和最后一个相同，第二个和倒数第二个相同，等等...

空箱的定义

我不希望任何垃圾箱是空的。如果您查看前面的示例，第一行和最后一行都有一个空容器。

Answer 1

看来我自己找到了解决办法

我改编了 this Whosebug answer 中的 Ruby 代码以满足我的需要：

class Array
  def distribute_to_bins(bins_left)
    Enumerator.new do |yielder|
      if self.empty?
        yielder.yield([])
      else

        # If there is only one bin left, fill all remaining items in it
        min_elements_in_bin = if bins_left == 1
                                self.size
                              else
                                1
                              end
        # Make sure that there are sufficient items left to not get any empty bins
        max_elements_in_bin = self.size - (bins_left - 1)

        (min_elements_in_bin..max_elements_in_bin).to_a.each do |number_of_elements_in_bin|
          self.drop(1).combination(number_of_elements_in_bin - 1).map { |vs| [self.first] + vs }.each do |values|
            (self - values).distribute_to_bins(bins_left - 1).each do |group|
              yielder.yield([values] + group)
            end
          end
        end
      end
    end
  end
end

像这样执行：

pp (1..5).to_a.distribute_to_bins(3).to_a

将产生所有可能性，没有空箱也没有重复：

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

Answer 2

这种划分的数目称为第二类斯特林数。 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 保持计算可行：

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)

例如：

>>> 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]]

效率相当高：将 10 个对象的 42,525 个分区生成到 5 个箱中只需不到一秒的时间。

Bin packing bruteforce 没有重复和空箱

Bin packing bruteforce without duplicates and empty bins

algorithm

brute-force

bin-packing