使用Ruby生成多重集的分區

Question

我想要獲得多重集（某些元素相同且彼此不可區分）的所有可能分區（聯合是原始集的集合的不相交子集）。

簡單的情況下，當想要產生一個簡單集合的分區，其中沒有多重性的元素，換句話說，所有元素都是不同的。對於這種情況，我發現上StackOwerflow此Ruby代碼，這是非常有效的，因爲不存儲所有可能的分區，但是它們產生一個塊：

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()方法以使用多重集合，或者如何以有效的方式過濾出相同的分區和重複？這些相同的分區是否總是以連續的方式彼此跟隨？

我的目標是將具有不同長寬比的圖像組織爲蒙太奇，並且蒙太奇的圖片行將是那些設置的分區。我想盡量減少圖像行之間的高度差異（或等效的標準偏差），但很多時候有相同縱橫比的圖像，這就是爲什麼我試圖處理多重圖像。

屈服不partitons而是一個多重的powersets（所有possibe子集），通過簡單的memoization過濾掉重複：

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