7

配列がある場合:

a = [1,2,3]

各サブセットの要素が一意になるように、配列のサブセットをランダムに選択するにはどうすればよいですか? つまりa、可能なサブセットは次のようになります。

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

a の実際のサイズは非常に大きいため、可能なサブセットをすべて生成することはできず、非常に多くのサブセットがあります。現時点では、「ランダム ウォーク」のアイデアを使用しています。a の各要素について、「コインを投げ」、コインが表に出た場合はそれを含めますが、これが実際にスペースを均一にサンプリングするかどうかはわかりません。真ん中に偏っているように感じますが、中くらいのサイズの可能性がもっとあるので、これはパターンマッチングをしている私の心かもしれません.

正しいアプローチを使用していますか、またはランダムにサンプリングするにはどうすればよいですか?

(これは言語にとらわれず、「数学的な」質問であることは承知していますが、実際には Mathoverflow の資料ではないと感じました。実用的な回答が必要です。)

4

5 に答える 5

5

オリジナルの「コイントス」のアイデアを先に進めてください。可能性の空間を均一にサンプリングします。

「真ん中」に偏っているように感じますが、それは「真ん中」が可能性の数が最も多いからです。考えてみてください。要素がない可能性は1つだけであり、すべての要素がある可能性は1つだけです。1つの要素でNの可能性があり、（N-1）の要素でNの可能性があります。選択される要素の数が（N / 2）に近づくにつれて、可能性の数は非常に急速に増加します。

于 2012-01-19T21:52:53.150 に答える
1

乱数を生成し、それらをバイナリに変換して、元の配列からビットが 1 である要素を選択できます。これをArrayクラスのモンキー パッチとして実装します。

class Array
  def random_subset(n=1)
    raise ArgumentError, "negative argument" if n < 0
    (1..n).map do
      r = rand(2**self.size)
      self.select.with_index { |el, i| r[i] == 1 }
    end
  end
end

使用法：

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

通常、これはそれほど悪いパフォーマンスではありません。n は必要なサブセットの数、m は配列の長さである O(n*m) です。

于 2012-01-19T17:43:09.263 に答える
0

パワー セットからランダムな要素を選択する方法は次のとおりです。

my_array = ('a'..'z').to_a
power_set_size = 2 ** my_array.length
random_subset = rand(power_set_size)
subset = []
random_subset.to_i(2).chars.each_with_index do |bit, corresponding_element|
  subset << my_array[corresponding_element] if bit == "1"
end

これは、便宜上、実際の「ビット」とビット単位の操作ではなく、文字列関数を使用します。実際のビットを使用することで、より高速な (私が推測する) アルゴリズムに変えることができます。

それが行うことは、のパワーセットをとarrayの間の整数としてエンコードし、それらの整数の 1 つをランダムに (一様にランダムに) 選択することです。次に、ビットマスクを使用して整数を特定のサブセットにデコードします(1 = 要素がサブセットに含まれる、0 = 含まれない)。02 ** array.lengtharray

このようにして、アレイの電力セット全体に均一な分布が得られます。

于 2012-01-20T12:40:56.797 に答える
0 
a.select {|element| rand(2) == 0 }

要素ごとに、コインを 1 枚投げます。頭 ( == 0) の場合、それが選択されます。

于 2012-01-19T19:02:59.083 に答える
0

コイン投げはいいと思います。

ar = ('a'..'j').to_a
p ar.select{ rand(2) == 0 }

10 個の要素を持つ配列には、2**10 通りの組み合わせ ([ ] と 10 個の要素すべてを含む) があり、これは 10 回 (1 または 0) を超えません。パワーセットにはさらに多くの要素があるため、4、5、および 6 つの要素の配列がさらに出力されます。

于 2012-01-19T21:04:10.407 に答える