使用Ruby产生多集的分区 [英] Yielding partitions of a multiset with Ruby

问题描述

我想获得一个多集(某些元素相等且彼此不可区分)的所有可能分区(集合是原始集合的不相交子集).

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

  def分区(设置)yield []是否为set.empty?(0 ... 2 ** set.size/2).每个| i |份数= [[]，[]]set.each做|项|零件[i&1]<<物品i> == 1结尾partitions(parts [1])做| b |结果= [部分[0]] + b结果= result.reject做| e |空吗?结尾屈服结果结尾结尾结尾 

示例:

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

输出:

  [[1、2、3]][[2，3]，[1]][[1，3]，[2]][[3]，[1、2]][[3]，[2]，[1]] 

由于集合 [1,2,3] 有5种不同的分区(无论如何，钟形图编号:

解决方案

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

  arr = []partitions([1,1,2]){| e |arr<<}放arr.to_s#->[[[1，1，2]]，[[1，2]，[1]]，[[1，2]，[1]]，[[2]，[1，1]]，[[2]，[1]，[1]]把arr.uniq.to_s#->[[[1，1，2]]，[[1，2]，[1]]，[[2]，[1，1]]，[[2]，[1]，[1]]] 

I would like to get all the possible partitions (disjoint subsets of a set which union is the original set) of a multiset (some elements are equal and non-distinguishable from each other).

Simpler case when one would like to yield the partitions of a simple set, in which there are no elements with multiplicity, in other words all elements are different. For this scenario I found this Ruby code on StackOwerflow which is very efficient, as not storing all the possible partitions, but yielding them to a 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

Example:

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

outputs:

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

As there are 5 different partitioning of the set [1,2,3] (Bell-number anyway: https://en.wikipedia.org/wiki/Bell_number)

However the another set which is in fact a multiset contains elements with multiplicity, then above code doesn't work of course:

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

outputs:

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

One can see two identical partitions, denoted with *, which should be yielded only once.

My question is: how can I modify the def partitions() method to work with multisets too, or how can I filter out the identical partitionings, duplications in an efficient way? Are those identical partitionings coming always followed by each other in a consecutive manner?

My goal is to organize images with different aspect ratio to a montage, and the picture rows of the montage would be those set partitions. I would like to minimalize the difference of the heights between the picture rows (or the standard deviation equivalently) among the possible partitionings, but many times there are pictures with same aspect ratios this is why I try to deal with a multiset.

Yielding not partitons but powersets (all possibe subsets) of a multiset, filtering out the duplicates by simple memoization:

Montage optimization by backtracking on YouTube

解决方案

You could put it in an array and use 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]]]

这篇关于使用Ruby产生多集的分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！