Rénovation des partitions d'un multiset avec Ruby

Question

Je voudrais obtenir toutes les partitions possibles (sous-ensembles disjoints d'un ensemble dont l'union est l'ensemble d'origine) d'un multiset (certains éléments sont égaux et non distinguables les uns des autres).

Plus simple si l'on veut donner les partitions d'un ensemble simple, dans lequel il n'y a pas d'éléments avec multiplicité, en d'autres termes tous les éléments sont différents. Pour ce scénario, j'ai trouvé ce code Ruby on StackOwerflow qui est très efficace, ne pas stocker toutes les partitions possibles, mais les céder à un bloc:

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 

Exemple:

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

sorties:

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

Comme il y a 5 différents répartition de l'ensemble [1,2,3] (Bell numéro de toute façon: https://en.wikipedia.org/wiki/Bell_number)

Cependant, l'autre ensemble qui est en fait un multiset contient des éléments avec la multiplicité, puis au-dessus du code ne fonctionne pas bien sûr:

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

sorties:

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

On peut voir deux partitions identiques , notée avec *, qui ne devrait être donnée qu'une seule fois.

Ma question est: comment puis-je modifier la méthode def partitions() pour travailler avec des multisets aussi, ou comment puis-je filtrer les partitionnements identiques, les duplications de manière efficace? Ces cloisonnements identiques sont-ils toujours suivis les uns par les autres de manière consécutive?

Mon objectif est d'organiser des images avec différents formats dans un montage, et les rangées d'images du montage seront ces partitions définies. Je voudrais minimiser la différence de hauteur entre les rangées d'images (ou l'écart-type de manière équivalente) parmi les partitions possibles, mais plusieurs fois il y a des images avec les mêmes proportions, c'est pourquoi j'essaie de traiter un multiset.

Cédant pas partitons mais spécialisations (tous les sous-ensembles de possibe) d'un multiset, filtrant les doublons par un simple memoization:

Montage optimization by backtracking on YouTube

Answer 1

Vous pouvez le mettre dans un tableau et utiliser 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]]]