arrays - 使用 Ruby 生成多重集的分区

Question

我想获取多重集的所有可能的分区(集合的不相交子集，其中并集是原始集)(某些元素是相等的并且彼此不可区分)。

更简单的情况，当人们想要生成一个简单集合的分区时，其中不存在具有多重性的元素，换句话说，所有元素都是不同的。对于这种情况，我在 StackOwerflow 上发现了这个 Ruby 代码，它非常高效，因为它不存储所有可能的分区，而是将它们生成一个 block :

def partitions(set)
  yield [] if set.empty?
  (0 ... 2 ** set.size / 2).each do |i|
    parts = [[], []]
    set.each do |item|
      parts[i & 1] << item
      i >>= 1
    end
    partitions(parts[1]) do |b|
      result = [parts[0]] + b
      result = result.reject do |e|
        e.empty?
      end
      yield result
    end
  end
end

示例:

partitions([1,2,3]){|e| puts e.inspect}

输出:

[[1, 2, 3]]
[[2, 3], [1]]
[[1, 3], [2]]
[[3], [1, 2]]
[[3], [2], [1]]

由于集合有 5 种不同的划分 [1,2,3] (无论如何，铃声号码:https://en.wikipedia.org/wiki/Bell_number)

然而，另一个集合实际上是一个多重集，包含具有多重性的元素，那么上面的代码当然不起作用:

partitions([1,1,2]){|e| puts e.inspect}

输出:

[[1, 1, 2]]
[[1, 2], [1]] *
[[1, 2], [1]] *
[[2], [1, 1]]
[[2], [1], [1]]

可以看到两个相同的分区，用*表示，应该只产生一次。

我的问题是:如何修改def partitions()也可以使用多重集的方法，或者如何以有效的方式过滤掉相同的分区、重复项？这些相同的分区是否总是以连续的方式彼此跟随？

我的目标是将不同长宽比的图像组织成蒙太奇，蒙太奇的图片行就是那些设置的分区。我想最小化可能的分区中图片行之间的高度差异(或等效的标准差)，但很多时候存在具有相同长宽比的图片，这就是我尝试处理多重集的原因。

产生的不是多重集的分区而是幂集(所有可能的子集)，通过简单的内存过滤掉重复项:

Montage optimization by backtracking on YouTube

Answer 1

您可以将其放入数组中并使用 uniq:

arr = []
partitions([1,1,2]) { |e| arr << e }

puts arr.to_s
#-> [[[1, 1, 2]], [[1, 2], [1]], [[1, 2], [1]], [[2], [1, 1]], [[2], [1], [1]]]

puts arr.uniq.to_s
#-> [[[1, 1, 2]], [[1, 2], [1]], [[2], [1, 1]], [[2], [1], [1]]]