11

3時間ぶっ通しで頭を悩ませているのですが、まだわからないのでこちらで質問させていただきます。(タイトルに Python と書きましたが、これはほとんどすべての言語に当てはまります)

固定長 n のビット配列 (ただし、定義された範囲内の整数の場合もあります) があるとします。たとえば、5 としましょう。

array=[0,1,1,0,0]

では、数値範囲 (ビットの場合は 2) で可能なすべての配列を生成するにはどうすればよいですか。

そう：

[0,0,0,0,0], [0,0,0,0,1], [0,0,0,1,0], [0,0,0,1,1] ...

ここで解決策を探してみましたが、似たようなものを常に見つけますが、問題は完全には解決されません。

これを解決するために、さまざまなループを試しましたが、常に 1 つの可能性を複数回取得するか (発生しないはずです)、可能性のあるすべての可能性を取得できません。

if ステートメント (組み合わせが既に存在するかどうかを確認するため) を使用してこれを行うことはできますが、それは非常に単純なようです。

ループのみを使用して、すべての可能性を取得する簡単な方法はありますか?

ありがとうございました

編集：これは以下で言及されているので、いいえ、これは宿題ではありません. これは、バイナリ状態のベイジアン ネットワークを実装するための研究用です。（オンオフ）。

4

5 に答える 5

16

Python では、このようなものにitertoolsを使用します

from itertools import product
for i in product([0,1], repeat=5): 
    print i

収量:

(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
etc...
于 2012-10-20T19:05:33.747 に答える
5

この問題に取り組むには、0から31（0b11111）にループし、バイナリ表現を固定長の配列に変換します。

これを言語でタグ付けしなかったので、サンプルコードを提供する方法がわかりませんが、そのアプローチは機能するはずです。

1: 00001
2: 00010
3: 00011
...
30:11110
31:11111

編集：この質問にPythonのタグを付けたのを見たところです。上記のアルゴリズムを実装するサンプルPythonコード：

listLength=5
for x in range(0,2**listlength):
    print(list(bin(x)[2:].zfill(listlength)))

プリントアウト：

['0', '0', '0', '0', '0']
['0', '0', '0', '0', '1']
['0', '0', '0', '1', '0']
['0', '0', '0', '1', '1']
['0', '0', '1', '0', '0']
['0', '0', '1', '0', '1']
['0', '0', '1', '1', '0']
['0', '0', '1', '1', '1']
['0', '1', '0', '0', '0']
['0', '1', '0', '0', '1']
['0', '1', '0', '1', '0']
['0', '1', '0', '1', '1']
['0', '1', '1', '0', '0']
['0', '1', '1', '0', '1']
['0', '1', '1', '1', '0']
['0', '1', '1', '1', '1']
['1', '0', '0', '0', '0']
['1', '0', '0', '0', '1']
['1', '0', '0', '1', '0']
['1', '0', '0', '1', '1']
['1', '0', '1', '0', '0']
['1', '0', '1', '0', '1']
['1', '0', '1', '1', '0']
['1', '0', '1', '1', '1']
['1', '1', '0', '0', '0']
['1', '1', '0', '0', '1']
['1', '1', '0', '1', '0']
['1', '1', '0', '1', '1']
['1', '1', '1', '0', '0']
['1', '1', '1', '0', '1']
['1', '1', '1', '1', '0']
于 2012-10-20T07:25:47.127 に答える
1

これは、あなたが求めていることを行うための一般化された再帰的擬似コードです。

array_combination is function (length, elements)
  if length < 1 
  then abort
  end if

  declare arrays as new array
  if length is 1 
  then
    loop for element in elements
      declare element_array as new array
      set element_array[0] to element
      append element_array to arrays
    end loop
  else
    loop for array in array_combination(length - 1, elements)
      loop for element in elements
        declare element_array as new array
        set element_array[0] to element
        append array to element_array
        append element_array to arrays
      end loop
      append array to arrays
    end loop
  end if
  return arrays
end function

与えられた例では、この関数を「array_combination(5, [1,0])」と呼びます。それを構築するためのより良い方法がありますが、a) 私は宿題をするのに年を取りすぎています.b) あなたの課題の制約を知りません.c) あなたがだまされたことをあまり明らかにしたくありません.

非常に無駄なメモリ割り当てとキャッシュの乱用に加えて、コードの繰り返しと一般的な部分式の削除の機会に注意してください。ただし、これは第 1 四半期のコンピューター サイエンスの課題であると想定しているため、おそらくあなたに不利になることはありません。

于 2012-10-20T07:58:51.983 に答える