4

重複の可能性：
0から上限NまでのK個の非反復整数のリストを効率的に生成するにはどうすればよいですか？

以下とは対照的に、[0,8000]の範囲で1000個の異なるランダム整数を生成するためのいくつかの代替方法は何ですか。

  1. 素朴な方法：数値を生成し、それがすでに配列にあるかどうかを確認します。O（n ^ 2）
  2. 線形シャッフル：シーケンス0〜8000を生成し、シャッフルし、最初の1000を取得します。O（n）
4

5 に答える 5

12

スワップを使用して実装された部分的なFisher-Yatesシャッフルを使用できます。このアルゴリズムの優れた機能の1つは、kスワップ後に停止した場合、最初の数値が完全なセットからkのサイズのランダムなサンプルになることです。k

于 2010-04-04T21:56:34.307 に答える
2

0から8000までの数字を含むリストを作成できます。

次に、1000回ループすると、0からリストの長さまでの乱数が生成されます。

その要素をリストから削除し、出力リストに追加します。

要素を削除することにより、選択が一意であることを確認します。

while (outputList.Count < 1000)
{
    index = random.Next(0, inputList.Count);
    outputList.Add(inputList[index]);
    inputList.RemoveAt(index);
}
于 2010-04-04T22:07:04.457 に答える
1

これは、Pythonで実装されたKnuthのArt of Programming（JonBentleyのProgrammingPearls経由）からのものです。

import random

# randomly select m numbers from n candidates    
def random_select(m, n):
    select = m
    result = []
    for i in xrange(n):
        if random.randint(0, n-i) < select:
            result.append(i)
            select -= 1
    return result

random_select(1000, 8000)

これにより、乱数のリストが番号順に生成されます。これは、0〜n（つまり、0〜8000）のすべての整数を反復処理し、確率（選択する残りの数/残りの候補の数）でそれらをランダムに選択することによって機能します。これはO（n）で実行されるため、nがmと比較して非常に大きい場合は試さないでください。たとえば、10億から10個の数値を選択します。長さnのリストのシャッフルに依存するソリューションとは異なり、結果リスト（m）といくつかのローカル変数以外のメモリは使用しません。

結果をランダムな順序で表示したい場合は、後でリストをシャッフルします。

于 2010-04-04T22:51:54.380 に答える
1

@Markが示唆しているように、部分的なフィッシャー-イェーツは、少しひねりを加えて、途中でスワップを保存します。
このように、結果リストO（m）と同じくらいのメモリを消費します。
また、範囲全体を列挙する他のソリューションのように、O（n）ではなくO（m）で実行されるため、より広い範囲で問題が発生することはありません。
このようにして、両方の長所を活かすことができます。

/// <summary>
/// Generates unique random numbers
/// <remarks>
/// Worst case memory usage is O(min((emax-imin)/2, num))
/// </remarks>
/// </summary>
/// <param name="random">Random source</param>
/// <param name="imin">Inclusive lower bound</param>
/// <param name="emax">Exclusive upper bound</param>
/// <param name="num">Number of integers to generate</param>
/// <returns>Sequence of unique random numbers</returns>
public static IEnumerable<int> UniqueRandoms(
    Random random, int imin, int emax, int num)
{
    int dictsize = num;
    long half = (emax - (long)imin + 1) / 2;
    if (half < dictsize)
        dictsize = (int)half;
    Dictionary<int, int> trans = new Dictionary<int, int>(dictsize);
    for (int i = 0; i < num; i++)
    {
        int current = imin + i;
        int r = random.Next(current, emax);
        int right;
        if (!trans.TryGetValue(r, out right))
        {
            right = r;
        }
        int left;
        if (trans.TryGetValue(current, out left))
        {
            trans.Remove(current);
        }
        else
        {
            left = current;
        }
        if (r > current)
        {
            trans[r] = left;
        }
        yield return right;
    }
}
于 2010-04-04T22:53:30.230 に答える
0

ソートなしのソート済みリスト、O（n）

整数をソートしたい場合は、多くの助けを借りて別の質問でこの答えにたどり着きました。指数変量を使用してそれを行うことができるため、並べ替えを回避できます。結果として、それはO（n）です：

Alokの回答とDanDyerのコメントから、デルタのセットに指数分布を使用すると、整数の一様分布が順番に得られることがわかります。

したがって、数値の生成を開始し、最後にスケーリングします。デルタに1を追加すると、値を繰り返さないようになります。

import random,sys,math

def genSortedInts(mini,maxi,vals):
    running = 0
    deltas = [random.expovariate(1.0) for i in range(0,vals+1)]
    floats = []
    for d in deltas:
        running += d
        floats.append(running)
    upper = floats.pop()
    valRange = maxi-mini-(vals-1)
    ints = [mini+int(f/upper*valRange)+id for id,f in enumerate(floats)]
    return ints

if __name__ == "__main__":
    vals = 10
    maxi = 80
    mini = 0
    print(genSortedInts(mini,maxi,vals))

Python指数分布乱数ジェネレーターrandom.expovariate(1.0)の使用に注意してください（非常に便利です！）。ここでは、平均値1.0（argは1 /平均値）で呼び出されますが、スクリプトはシーケンスの最後の数値に対して正規化されるため、平均値自体は重要ではありません。

80までの10個の値の出力（フェアダイスロール）：

[3, 5, 10, 16, 25, 37, 41, 45, 57, 70]
于 2010-04-07T14:13:30.623 に答える