5

閉区間[1,5]で一様分布でランダム整数を生成する関数rand5（）が与えられます。rand5（）だけを使用して、[1,7]の整数を生成する関数rand7（）を作成するにはどうすればよいですか（これも均一に分散されています）。

  1. 私はstackoverflowを検索し、多くの同様の質問を見つけましたが、これとまったく同じではありません。
  2. 私の最初の試みはrand5（）+ 0.5 * rand5（）+ 0.5 * rand5（）でした。しかし、これは均一な確率で1から7までの整数を生成しません。任意の回答、または回答へのリンクは大歓迎です。
4

4 に答える 4

7

すべての：-に対して、常にいくつかの「スペア」要素があるため、呼び出しの数が制限されている場合、完全な一様分布を達成できないことにdraw5()注意してください。k5^k % 7 != 0

使用回数に制限のないソリューションは次のとおりです。draw5()

x1、x2の2つの数字を描きます。これには5*5=25の可能な結果があります。

25/7〜=3.57であることに注意してください。3 * 7 = 21の組み合わせを選択し、他のすべての4つの数字について、各組み合わせが[1,7]の1つの数字にマップされるようにします-再描画します。

例えば：

(1,1),(1,2),(2,1) : 1
(3,1),(1,3),(3,2): 2
(3,3),(1,4),(4,1): 3
(2,4),(4,2)(3,4): 4
(4,3), (4,4), (1,5): 5
(5,1), (2,5), (5,2) : 6
(5,3), (3,5), (4,5) : 7
(5,4),(5,5),(2,3), (2,2) : redraw
于 2012-07-03T05:19:55.477 に答える
4

簡単な方法は次のとおりです。

  1. rand5（）を使用して、集合{1、2、4、5}から3つのランダムな整数のシーケンスを生成します（つまり、生成された3つを破棄します）。
  2. 3つの数字すべてがセット{1、2}に含まれている場合は、シーケンスを破棄して手順1に戻ります。
  3. シーケンス内の各数値について、{1、2}を0に、{4、5}を1にマップします。これらを3ビット数値の3ビット値として使用します。すべてのビットを0にすることはできないため、数値は[1、7]の範囲になります。各ビットは等しい確率で0または1であるため、[1、7]の分布は均一である必要があります。
于 2012-07-03T05:20:40.913 に答える
2

しばらく考えなければなりませんでしたが、実際にはそれほど難しいことではありません。rand5 の代わりに、0 または 1 を出力する rand2 があると想像してください。

rand2() {
    if(rand5() > 2.5) return 1
    else return 0
}

rand2 を複数回使用してツリーを実行し、rand7 を取得します。たとえば、rand7 を開始すると、0 を与える rand2 のスロー後に [1,2,3,4,5,6,7] にある可能性があり、[1,2,3,4] にサブセット化され、別のスローの後、または1 である rand2 を [3,4] にサブセット化し、最終的に 1 をスローすると、rand7 の出力は 4 になります。一般に、このツリー トリックは、rand2 を取り、x が任意の整数である randx にマップするために機能します。

于 2012-07-03T05:22:16.420 に答える
2

これらの問題の多くに役立つ 1 つのメタトリックを次に示します。用語を何らかの方法で異なる方法で扱うとバイアスが導入されるため、各ステップでそれらをすべて同じように扱い、setでのみ操作を実行すると、困らないようにします。

rand5() を少なくとも 1 回呼び出す必要があります (明らかに!)。代わりに、7 つの可能性ごとに 1 回呼び出してみましょう。

In [126]: import random

In [127]: def r5():
   .....:     return random.randint(1, 5)
   .....: 

In [128]: [r5() for i in range(7)]
Out[128]: [3, 1, 3, 4, 1, 1, 2]

明らかに、これらの項のそれぞれは、これらの数値のいずれかである可能性が等しくありました..しかし、そのうちの 1 つだけがたまたま 2 であったため、ルールが「rand5() が 2 を返す項を選択する」であった場合、それはうまくいきます。または 4 か何かで、単純に十分長くループすると、それが発生します。そのため、機能するものを思いつく方法はたくさんあります。ここに (疑似コードで -- これはひどい Python です) 1 つの方法があります。

import random, collections

def r5():
    return random.randint(1, 5)

def r7():
    left = range(1, 8)
    while True:
        if len(left) == 1: 
            return left[0]
        rs = [r5() for n in left]
        m = max(rs)
        how_many_at_max = rs.count(m)
        if how_many_at_max == len(rs):
            # all the same: try again
            continue
        elif how_many_at_max == 1:
            # hooray!
            return left[rs.index(m)]
        # keep only the non-maximals
        left = [l for l,r in zip(left, rs) if r != m]

を与える

In [189]: collections.Counter(r7() for _ in xrange(10**6))
Out[189]: Counter({7: 143570, 5: 143206, 4: 142827, 2: 142673, 6: 142604, 1: 142573, 3: 142547})
于 2012-07-03T05:39:55.287 に答える