n要素の配列から '公平な組み合わせ'を得るには？

Question

我々は15（6C2）素子を有する2次元配列を得ることができるルビー、

[1, 2, 3, 4, 5, 6].combination(2).to_a 
#=> [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 3], 
# [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6], 
# [4, 5], [4, 6], [5, 6]] 

にcombination方法を使用。

私はこのような配列を返すfair_combination方法作成したい：すべての三つのサブアレイ（6の半分）は、すべての指定された要素を含むように

arr = [[1, 2], [3, 5], [4, 6], 
     [3, 4], [5, 1], [6, 2], 
     [5, 6], [1, 3], [2, 4], 
     [2, 3], [4, 5], [6, 1], 
     [1, 4], [2, 5], [3, 6]] 

を：

arr.each_slice(3).map { |a| a.flatten.sort } 
#=> [[1, 2, 3, 4, 5, 6], 
# [1, 2, 3, 4, 5, 6], 
# [1, 2, 3, 4, 5, 6], 
# [1, 2, 3, 4, 5, 6], 
# [1, 2, 3, 4, 5, 6]] 

これは、配列が進むにつれて可能な限りさまざまな要素を使用することで、一種の「公正」になります。

それがより一般的にするために、次のように何が満たす必要がある：あなたが最初から配列に従って、各番号が表示された回数をカウントしたよう

（1）、いずれかの時点でそれはのように平らにしてくださいできるだけ;

(1..7).to_a.fair_combination(3) 
#=> [[1, 2, 3], [4, 5, 6], [7, 1, 4], [2, 5, 3], [6, 7, 2], ...] 

最初の7つの数字は[1,2、...、7]となります。したがって、次の7つの数字も行います。

（2）AがBと同じ配列に入ると、可能であればAはBと同じ配列になりたくない。

(1..10).to_a.fair_combination(4) 
#=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 1, 5], [2, 6, 9, 3], [4, 7, 10, 8], ...] 

"フェアコンビネーション"を作成するアルゴリズムはありますか？

Answer 1

ナイーブな実装は次のようになります。率直に言って

class Integer 
    # naïve factorial implementation; no checks 
    def ! 
    (1..self).inject(:*) 
    end 
end 

class Range 
    # constant Proc instance for tests; not needed 
    C_N_R = -> (n, r) { n.!/(r.! * (n - r).!) } 

    def fair_combination(n) 
    to_a.permutation 
     .map { |a| a.each_slice(n).to_a } 
     .each_with_object([]) do |e, memo| 
      e.map!(&:sort) 
      memo << e if memo.all? { |me| (me & e).empty? } 
     end 
    end 
end 

▶ (1..6).fair_combination(2) 
#⇒ [ 
# [[1, 2], [3, 4], [5, 6]], 
# [[1, 3], [2, 5], [4, 6]], 
# [[1, 4], [2, 6], [3, 5]], 
# [[1, 5], [2, 4], [3, 6]], 
# [[1, 6], [2, 3], [4, 5]]] 
▶ (1..6).fair_combination(3) 
#⇒ [ 
# [[1, 2, 3], [4, 5, 6]], 
# [[1, 2, 4], [3, 5, 6]], 
# [[1, 2, 5], [3, 4, 6]], 
# [[1, 2, 6], [3, 4, 5]], 
# [[1, 3, 4], [2, 5, 6]], 
# [[1, 3, 5], [2, 4, 6]], 
# [[1, 3, 6], [2, 4, 5]], 
# [[1, 4, 5], [2, 3, 6]], 
# [[1, 4, 6], [2, 3, 5]], 
# [[1, 5, 6], [2, 3, 4]]] 
▶ Range::C_N_R[6, 3] 
#⇒ 20 

、私は、この関数は10と4のためにどのように振る舞うべきかを理解していませんが、とにかくこの実装はあまりにもメモリは大きな範囲で適切に動作するために消費している（私のマシンでそれは大きさの範囲にはまり> 8）

1がの賛成でありpermutationを取り除く必要があり、より堅牢なソリューションにこれを調整するには、「スマートCONCATENATE順列配列。」

これは初心者にとってはうれしいです。

Answer 2

最高のソリューションを提供することは保証されませんが、十分なものが得られます。

各ステップで、最小の高さの項目のセットである最小のサブプールを選択します。これには、まだ選択する組み合わせがあります（高さは、アイテムが以前に使用された回数です）。例えば

、列挙子は

my_enum = FairPermuter.new('abcdef'.chars, 4).each 

最初の繰り返しは、この時点で

my_enum.next # => ['a', 'b', 'c', 'd'] 

を返すことがあります。それらの文字は、高さ1を持っていますが、作るために、高さ0の十分な文字がないことしましょう組み合わせたので、次のすべてのためにそれらのすべてを取る：

my_enum.next # => ['a', 'b', 'c', 'e'] for instance 

今すぐ高さaため2、bとc、dとeため1、およびfため0あり、まだ最適なプールが満杯最初のセットです。

これは、実際には大きなサイズの組み合わせには最適化されていません。反対に、組み合わせのサイズが初期セットのサイズの半分以下であれば、アルゴリズムはまともです。 2

[[4, 5], [2, 3], [3, 5], 
[1, 2], [1, 4], [1, 5], 
[2, 4], [3, 4], [1, 3], 
[2, 5]] 

5上の公正な組み合わせの2

[[4, 6], [1, 3], [2, 5], 
[3, 5], [1, 4], [2, 6], 
[4, 5], [3, 6], [1, 2], 
[2, 3], [5, 6], [1, 6], 
[3, 4], [1, 5], [2, 4]] 

6上結果の公正な組合せの4

[[1, 2, 4, 6], [3, 4, 5, 6], [1, 2, 3, 5], 
[2, 4, 5, 6], [2, 3, 5, 6], [1, 3, 5, 6], 
[1, 2, 3, 4], [1, 3, 4, 6], [1, 2, 4, 5], 
[1, 2, 3, 6], [2, 3, 4, 6], [1, 2, 5, 6], 
[1, 3, 4, 5], [1, 4, 5, 6], [2, 3, 4, 5]] 

6上結果の公正な組み合わせについて

class FairPermuter 
    def initialize(pool, size) 
    @pool = pool 
    @size = size 
    @all = Array(pool).combination(size) 
    @used = [] 
    @counts = Hash.new(0) 
    @max_count = 0 
    end 

    def find_valid_combination 
    [*0..@max_count].each do |height| 
     candidates = @pool.select { |item| @counts[item] <= height } 
     next if candidates.size < @size 
     cand_comb = [*candidates.combination(@size)] - @used 
     comb = cand_comb.sample 
     return comb if comb 
    end 
    nil 
    end 

    def each 
    return enum_for(:each) unless block_given? 
    while combination = find_valid_combination 
     @used << combination 
     combination.each { |k| @counts[k] += 1 } 
     @max_count = @counts.values.max 
     yield combination 
     return if @used.size >= [*1..@pool.size].inject(1, :*) 
    end 
    end 
end 

結果

12を超える5の組み合わせを取得：

 1.19 real   1.15 user   0.03 sys