0

アイテムのセットを別のセットにかなり均等に分散させようとしており、役立つアルゴリズムを探しています。

たとえば、グループ A には 42 個のアイテムがあり、グループ B には 16 個のアイテムがあります。B が A 内にかなり均等に分散されるように、両方のグループを混ぜ合わせたいと考えています。したがって、マージされたグループは次のようになります。 A が B の倍数だった場合ですが、それは私のニーズにはあまり当てはまりません。

4

3 に答える 3

0

あるセットから他のセットのアイテムの間にあるアイテムの数を取得することから始めることができます。

float number_between = bigger_set.size() / smaller_set.size();

アキュムレータ ( で初期化number_between) からループごとに 1 を減算し、このアキュムレータが 0 を下回るたびに小さいセットからアイテムを挿入し、 で更新しますnumber_between。

float accumulator = number_between;
foreach(item : bigger_set) {
  result.add(item);
  accumulator = accumulator - 1;
  if (accumulator < 0) {
      result.add(next from smaller_set);
      accumulator = accumulator + number_between;
  } 
}

編集

への変更：

float number_between = (bigger_set.size() +1) / smaller_set.size();

より大きなリストが結果リストの開始と終了の両方であることを確認したい場合。

編集2

浮動小数点演算を使用すると、丸めやアンダーフロー エラーが発生する可能性があることに注意してください。

たとえば、IEEE 単精度 (24 ビット ~ 7 桁の仮数部) を使用していて、大きなリストが小さなリストよりも 10^7 倍以上大きい場合、行accumulator = accumulator - 1はアンダーフローします (そして、より大きなセットによって完全に作成された結果を取得し、より小さなセットは作成しません)。

また、丸めによって、小さいリストが使い果たされたときに、小さい方のリストからさらに項目を引き出そうとする可能性があります。

于 2015-05-05T21:45:20.140 に答える
0

1) 2 つのグループを連結し、組み合わせたグループから単純なサンプリングを行うことができます。たとえば、要素をシャッフルし、シャッフルされた組み合わせセットを反復処理することです。

2) 順番に実行したい場合は、確率size(A) / (size(A) + size(B))およびsize(B) / (size(A) + size(B))で各グループからサンプリングできます。ここで、size(A)およびsize(B)は、それぞれグループ A および B 内のまだサンプリングされていない要素の現在の数です。つまり、U が Uniform(0,1) 乱数ジェネレーターからのドローである場合:

if U <= size(A) / (size(A) + size(B))
   randomly draw next observation from A
else
   randomly draw next observation from B

どちらのアプローチでも、AとBは範囲全体に均一に分散されます。これは、「かなり均一な分散」の統計的記述です。

言語を指定しなかったので、Ruby での両方のアプローチの具体的な実装を次に示します。出力の長さを適切に保つために、セットのサイズを半分にカットしました。明らかに、ランダム性の使用により、これらは実行されるたびに異なる結果を生成します。

最初のアプローチ:

a = ['A'] * 21
b = ['B'] * 8
c = (a + b).shuffle
puts c.join(',')

たとえば、次の出力が生成されます。

A,A,A,A,A,B,A,A,A,A,A,B,B,B,A,B,A,A,A,A,A,A,A,A,A,B,B,A,B

2 番目のアプローチ:

a = ['A'] * 21
b = ['B'] * 8
c = []    
while a.length > 0 || b.length > 0
  c << (rand <= (a.length / (a.length + b.length).to_f) ? a.shift : b.shift)
end    
puts c.join(',')

たとえば、次の出力が生成されます。

A,A,B,A,A,A,B,B,A,A,A,A,A,A,A,B,B,B,A,A,A,B,A,A,A,B,A,A,A
于 2015-05-05T21:45:36.060 に答える