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

因为集合 [1,2,3] 有 5 个不同的分区(总之铃号: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]]]