5

から指定された範囲内の乱数を返す関数が必要なという課題に遭遇しました0 - X。それだけでなく、返される番号が一意である必要があります。関数への以前の呼び出しで既に返された数値を複製しません。

オプションで、これが行われた場合 (たとえば、範囲が「使い果たされた」)、範囲内の乱数を返すだけです。

これを行うにはどうすればよいでしょうか？

4

4 に答える 4

6

これはそれを行う必要があります：

function makeRandomRange(x) {
    var used = new Array(x),
        exhausted = false;
    return function getRandom() {
        var random = Math.floor(Math.random() * x);
        if (exhausted) {
            return random;
        } else {
            for (var i=0; i<x; i++) {
                random = (random + 1) % x;
                if (random in used)
                    continue;
                used[random] = true;
                return random;
            }
            // no free place found
            exhausted = true;
            used = null; // free memory
            return random;
        }
    };
}

使用法：

var generate = makeRandomRange(20);

var x1 = generate(),
    x2 = generate(),
    ...

動作しますが、x 番目の乱数が生成されるとパフォーマンスが低下します。リスト全体で空き場所を検索します。O(1) 内の一意の(繰り返しのない)乱数? 、パフォーマンスが向上します。

function makeRandomRange(x) {
    var range = new Array(x),
        pointer = x;
    return function getRandom() {
        pointer = (pointer-1+x) % x;
        var random = Math.floor(Math.random() * pointer);
        var num = (random in range) ? range[random] : random;
        range[random] = (pointer in range) ? range[pointer] : pointer;
        return range[pointer] = num;
    };
}

( jsfiddle.net のデモ)

一意の番号の「グループ」を 1 つだけ生成する拡張バージョン:

function makeRandomRange(x) {
    var range = new Array(x),
        pointer = x;
    return function getRandom() {
        if (range) {
            pointer--;
            var random = Math.floor(Math.random() * pointer);
            var num = (random in range) ? range[random] : random;
            range[random] = (pointer in range) ? range[pointer] : pointer;
            range[pointer] = num;
            if (pointer <= 0) { // first x numbers had been unique
                range = null; // free memory;
            }
            return num;
        } else {
            return Math.floor(Math.random() * x);
        }
    };
}

(デモ)

于 2012-08-04T14:24:35.733 に答える
3

あなたは素晴らしいプログラミングの答えを得ました。これは、パノラマを完成させるためのより理論的なフレーバーを備えたものです:-)

あなたの問題は「サンプリング」または「サブセットサンプリング」と呼ばれ、これを行う方法がいくつかあります。Nフレームをサンプリングする範囲 (つまり)N=X+1をMサンプルのサイズ (選択する要素の数) とします。

于 2012-08-04T22:16:34.553 に答える
2

この関数を書きました。生成された数値の履歴を含む独自の配列を保持し、最初の重複を防ぎ、範囲内のすべての数値が一度出力された場合は乱数を出力し続けます。

// Generates a unique number from a range
// keeps track of generated numbers in a history array
// if all numbers in the range have been returned once, keep outputting random numbers within the range
var UniqueRandom = { NumHistory: new Array(), generate: function(maxNum) {
        var current = Math.round(Math.random()*(maxNum-1));
        if (maxNum > 1 && this.NumHistory.length > 0) {
            if (this.NumHistory.length != maxNum) {
                while($.inArray(current, this.NumHistory) != -1) { current = Math.round(Math.random()*(maxNum-1)); }
                this.NumHistory.push(current);
                return current;
            } else {
                //unique numbers done, continue outputting random numbers, or we could reset the history array (NumHistory = [];)
                return current;
            }
        } else {
            //first time only
            this.NumHistory.push(current);
            return current;
        }
    }
};

ここに働くフィドルがあります

これが誰かに役立つことを願っています！

編集: 以下のPointyで指摘されているように、範囲が広いと遅くなる可能性があります (ここでは 0-1000 の範囲を超えるフィドルがあり、正常に動作しているようです)。でも; それほど大きな範囲は必要ありませんでしたので、膨大な範囲を生成して追跡する場合、この関数は実際には適していない可能性があります。

于 2012-08-04T12:48:21.593 に答える