1

範囲内で繰り返しなしでランダムな値を生成する効率的なアルゴリズムを探しています。

擬似コード: (クラス Rand 内)

  Rand(long from, long to) {
    this.from = from;
    this.to = to;
    // ...
  }

  long getNumber() {

    // returns a random number in the [from, to] range
    //  which has never been returned before
  }

使用法：

  Rand r = new Rand(1, 100000000);

  long x = r.getNumber();
  long y = r.getNumber();
  ...

r.getNumber() から返される数値は、以前に返された数値とは常に異なる必要があります。
もちろん、to - from + 1数値が返された場合、アルゴリズムは再び開始する必要があります (またはエラーが発生します - とにかく重要ではありません)。

範囲が非常に大きくなる可能性があるため、ランダムに配置された配列 (最初は[from, to]数値を含む) はメモリをオーバーフローする可能性があることに注意してください。

4

7 に答える 7

5

暗号は 1 対 1 のマッピングであり、それ以外の場合は復号化できません。したがって、任意のブロック暗号は、数値 0、1、2、3、4、5、... を異なる n ビットの数値にマッピングします。ここで、n は暗号のブロック サイズ (ビット単位) です。

シンプルな 4 ラウンドの Feistel サイファーを任意の (偶数の) ブロック サイズで組み立てるのは比較的簡単です。たった 4 回のラウンドでは高速ですが安全ではありません。または、必要なブロックサイズをほぼすべて持つことができるHasty Puddingサイファーを使用してください。

使用する暗号が何であれ、数値 0、1、2、... を暗号化して、出力ブロックを見てください。必要な範囲外の結果は破棄でき、すべての結果が一意であることが保証されます。

于 2011-08-19T12:09:39.233 に答える
1

出発点についてのいくつかの考え：

1）1..Nの順列である関数f（x）があり、Nが範囲よりも大きいとします。範囲内のxに適用すると、範囲外の値が生成される可能性があります。不正な値に対してfを再度呼び出すだけで、範囲内の順列を定義できます。シーケンスx、f（x）、f ^ 2（x）、f ^ 3（x）は最終的に循環する必要があり、最悪の場合はxに戻るため、最終的には正当な値になります。

2）特別なNのNオブジェクトで可能なすべての順列を生成できるスイッチングネットワークがあります。1つの例はhttp://en.wikipedia.org/wiki/Clos_network#Bene.C5.A1_network_.28m_.3D_n_.3D_2です。 29（面白いURL-Benesネットワーク）。スイッチをランダムに設定することで、N個のオブジェクトで任意の順列を取得できます。Nは2の累乗である必要があると思います。K個のスイッチがあるので、それらを設定する2 ^ Kの方法があります。これは、Mがないことを意味します。確率は同じですが、これを気にしないか、これを複数回繰り返すことで非ランダム性を最小限に抑えることができます。

3）多くの異なる基本順列を何度も適用することでほぼランダム性を実現する準備ができている場合は、範囲全体にmod Nを交互に追加してから、範囲をサブ範囲に分割してみてください。範囲内で、いくつかのkモードpを乗算することによって生成された順列を適用します。個々のステップは十分に適用し、十分に多様化することでかなり基本的ですが、特にパラメーターをランダムに選択した場合、結果はほぼランダムになることが期待されます。

于 2011-08-19T06:03:20.310 に答える
1

これを行う1つの方法は、fromとtoの間の番号のリストを生成し、バッグが空になるまでこれらをランダムに削除し、バッグが空になると再入力することです。広い範囲のストレージを節約するために、最初は重複を選択する可能性が低いはずなので、選択した番号をある時点まで記録できます（重複が選択された場合は再選択）。最適な遷移点を決定することは、おそらく経験的な演習になるでしょう。

編集：もう少し考え。

本当に広い範囲の場合、それでもメモリの制限の下で優れたパフォーマンスを提供することはできません。1つのアイデアは、候補を数値のリストとしてではなく、間隔として保存することです。したがって、最初は、からとへのどちらかを選択して、x1を取得します。次回は、間隔の長さに比例した確率で、最初のサブインターバルまたは2番目のサブインターバルの数値から選択します。各ステップで、長さがゼロの間隔を削除します。これには、M + 2整数（最悪の場合）を格納する必要があります。ここで、Mは描画の数、またはN / 2は大きなN（最悪の場合）の場合は漸近的に格納されます。ここで、Nは初期間隔サイズです。しかし、誰かが私を再確認するかもしれません。

于 2011-08-19T03:33:27.890 に答える
1

Rで解決策を求めているふりをします（タグによる）。あなたがやろうとしているのは、置換なしでサンプリングすることです。Rには、という関数がありsampleます。ここでは、30 個の値 (1、2、3... 30) のベクトルをサンプリングしています。一度描画した数値は置き換えられません。シードを設定すると、他のマシンでこれを再現できるようになります (「参考文献」を参照set.seed)。

ランダム性を示すために、これを何度も実行しました。

> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  9 16 13 20 12  3  1  5 28  7
> sample(x = 1:30, size = 10, replace = FALSE)
 [1] 22 11 26 29 20  1  3  6  7 10
> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  1 11 16  7 22 26  3 25  8  9
> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  7 17  3 22 21 24 27 12 28  2
> sample(x = 1:30, size = 10, replace = FALSE)
 [1] 30 21 23  2 27 24  3 18 25 19
> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  4  6 11 16 26  8 17 22 23 25
于 2011-08-19T11:42:15.433 に答える
1

間隔のすべての数値が最終的に表示される必要がない場合は、線形合同ジェネレーターを使用できます。

int getNumber() {
    seed = (seed * A + C) mod (to-from);
    return seed + to;
}

それは定期的で、シードが初期値と等しくなると新しい期間が始まり、期間の長さは A と C の選択に依存します。

長所: O(1) の時間と空間、短所: 間隔のすべての数値が表示されるわけではありません。

長さ 2^m の間隔については、http://en.wikipedia.org/wiki/Linear_feedback_shift_registerを参照してください。 (1 つを除く) が出力に表示されます。

于 2011-08-19T04:34:57.093 に答える
1

このように進めることができます（Pythonで）：

xrange を作成し、そこから k 個のランダム要素を選択して、それを RandomGenerator として使用します。

import random

def randomFromTo(FROM,TO,k): #k is the number of sample you want to generate
    m= random.sample(xrange(FROM,TO),k)
    return (i for i in m)

Generator は FROM から TO までのすべての数をランダムに生成し、k 個を超える数を生成すると失敗します。

この例では、次のようになります。

RandomGenerator=randomFromTo(10,1000000000,12)

for k in range(12): 
    print RandomGenerator.next()

あなたが得る

57625960
50621599
2891457
56292598
54608718
45258991
24112743
55282480
28873528
1120483
56876700
98173231
于 2011-08-19T10:35:32.413 に答える
1

@rossum は次のように述べています。

暗号は 1 対 1 のマッピングであり、それ以外の場合は復号化できません。したがって、任意のブロック暗号は、数値 0、1、2、3、4、5、... を異なる n ビットの数値にマッピングします。ここで、n は暗号のブロック サイズ (ビット単位) です。

そのため、xor 暗号化やビットごとのリバースでさえ、いくつかの目的には十分です。

そして、単純な 1 対 1 暗号化として xor とビットごとの反転を使用する php 関数を次に示します。

これは、すべての値の入力が保証され、同一の値がない疑似乱数ジェネレーターです。n:0..63 を指定すると、ランダムな 0..63 が提供されます。

0..63、0..127 などの 2^i 範囲のみを受け入れます。

暗号学的に安全ではないなど、ランダムです。

このような関数は、ガベージ コレクション ルーチンに非常に適しています。ランダムに実行しても、同じ領域を 2 回クリーニングしようとしないためです。

 function math_random_filled($n,$bits,$seed)
 {
   //bits: examples: 6=0..63, 8=0..255, 10: 0..1023
   //n: 0<= n <2^$bits
   //seed: any string or number

   //generate xor: crc32 + bit mask
   $xor= crc32($seed.'internalseed') & ~(-1<<$bits);
   //xor
   $r=intval($n)^$xor;
   //bitwise reverse
   $r=bindec(strrev(str_pad(decbin($r),$bits,'0',STR_PAD_LEFT)));
   return $r;
 }

 //demonstration
 $bits=6;
 $min=0;
 $max=pow(2,$bits)-1;
 $count=$max-$min+1;
 for($n=0;$n<=$max;$n++)
 {
   $r=math_random_filled($n,$bits,$seed='someseed');
   echo " $r ";
   $ar[$r]=1;
 }


 $set=0;
 for($n=0;$n<=$max;$n++)
   if(isset($ar[$n])) $set++;


 echo "\n"."bits: $bits,  count: $count, set: ". $set."\n\n";

出力例:

 37  5  53  21  45  13  61  29  33  1  49  17  41  9  57  25  39  7  55  23  47  15  63  31  35  3  51  19  43  11  59  27  36  4  52  20  44  12  60  28  32  0  48  16  40  8  56  24  38  6  54  22  46  14  62  30  34  2  50  18  42  10  58  26 

bits: 6,  count: 64, set: 64

ここでコードをphpサンドボックスでテストできます

これは別のものですが、2 のべき乗だけでなく、任意の範囲を受け入れます。

function math_random_filled_arithmetical($n,$max,$seed)
    {
    /*
    - produces 0..max, repeatable, unique, one-to-one mapped random numbers
    - uses arithmetic operations to imitate randomness
    - $n: 0<=$n=<$max
    - $max: any integer, not only power of two
    - $seed: any string or number
    */
    $n=intval($n);
    $max=intval($max);
    $opt1=$n;
    $opt2=$max-$n;
    $n2=min($opt1,$opt2);
    $reverseit=crc32($seed.'internalseed'.$n2)&1;
    if($opt1>$opt2) $reverseit=!$reverseit;
    $max2=floor(intval($max-1)/2);
    //echo "n:$n, max:$max,n2:$n2,max2:$max2,reverseit:$reverseit\n";
    if($max>=3)
    if($opt1!=$opt2)
        $n2=math_random_filled_arithmetical($n2,$max2,$seed.'*');
    $res=$reverseit? $max-$n2:$n2;
    $res=intval(fmod($res+(crc32($seed)&(1<<30)),$max+1));
    //echo "n:$n, max:$max, res:$res\n";
    return $res;
    }


//demonstration
$max=41;//-- test a max value 
for($n=0;$n<=$max;$n++)
    {
    $r=math_random_filled_arithmetical($n,$max,$seed='someseed');
    $ar[$r]=1;
    echo " $r ";
    }
$filled=0;
for($n=0;$n<=$max;$n++)
    if(isset($ar[$n])) $filled++;
echo "\n count: ".($max+1).", filled: ". $filled."\n";

出力例:

 20  19  18  17  33  32  37  36  14  13  31  34  35  26  16  11  12  3  39  40  0  41  1  2  38  29  30  25  15  6  7  10  28  27  5  4  9  8  24  23  22  21 
 count: 42, filled: 42

関連するphpサンドボックスはこちら

于 2013-04-08T04:04:47.150 に答える