0

我想找到所有将n元素分配到b垃圾箱但没有“重复”和空垃圾箱的方法。

例子

如果我有n = 3元素和b = 2垃圾箱并从这个 stackoverflow 线程Bin 打包蛮力方法应用蛮力方法，我会得到以下结果：

[[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 的顺序：first 和 last 相同，2nd 和 2nd to last 相同，等等...

空箱的定义

我不希望任何垃圾箱是空的。如果你看前面的例子，第一行和最后一行有一个空的 bin。

4

2 回答 2

1

这种划分的数目称为第二类斯特林数。有关这些数字的Wikipedia 文章给出了递归关系，可以对其进行修改以提供用于生成这些分区的递归函数。以下 Python 实现使用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 中只需不到一秒的时间。

于 2015-07-26T17:09:47.247 回答
0

好像我自己找到了解决方案。

我改编了这个 stackoverflow 答案中的 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]]]
于 2015-07-26T14:18:38.063 回答