Javascript: Исключить элемент из случайного набора - (любознательность)

Question

У меня есть вопрос, касающийся JavaScript Math.random():

Я (для игры я строй) случайным образом генерировать каждое число из заданного набора (т.е. от 0 до 1000), и каждый раз, когда мне приходится генерировать число, я должен проверить, был ли этот номер уже «сгенерирован».

Решение довольно простое мышление о простом алгоритме, который проверяет, присутствует ли случайное целое в сгенерированном наборе. Он зацикливает числа, пока не найдет их. сниппета ниже:

/* ... */ 
for(var i = 0; i<upperBound; i++){ 
    var randN = Math.floor(Math.random()*upperBound); 
    while(myRandomNumbers.contains(randN)){ 
     loops++; 
     randN = Math.floor(Math.random()*upperBound); 
    } 
    myRandomNumbers.push(randN); 
} 
/* ... */ 

running example here

Я хотел бы знать: это лучший способ для достижения этой цели? или есть ли какие-либо способы, а не цикл, пока он не породит «хороший» номер, чтобы исключить конкретный набор в случайном генерации?

Спасибо большое всем!

Answer 1

1. Сформировать набор чисел в порядке.
2. Сортировка списка в случайном порядке.

Вот пример с использованием naive, biased sort:

for (var nums=[],i=0;i<1000;++i) nums[i]=i+1; 
nums.sort(function(){ return Math.random()-0.5 }); 

Тогда вы можете просто pop() номера прочь nums, чтобы получить следующий «случайный» номер, гарантированно никогда не использовались ранее.

Answer 2

Если ваш диапазон номеров не является чрезмерно большим, вы можете просто сгенерировать список со всеми числами, рандомизировать его, а затем выбрать один за другим.

Вот быстрый хак вашего примера реализации, чтобы показать этот метод в действии: http://www.jsfiddle.net/ZTLt9/8/

Answer 3

насчет массива булевых 1001 больших.

Если вы хотите, чтобы проверить числа было сформировано, все, что вам нужно сделать, это проверить номер на этой позиции в массиве:

if (!arr[randomnumber]){ 
    arr[randomnumber] = true; 
} 

В конце, вы можете сканировать массив, чтобы найти номера, которые вам нужны.

У этого есть дополнительный побочный эффект при сортировке ваших номеров, так как сканирование выберет их по порядку.

Нечто похожее на это было предметом одного из моих постов в блоге: http://www.jameswiseman.com/blog/2010/05/27/generate-and-sort-lottery-numbers/

Answer 4

Я бы создать массив и случайным образом перетасовать его:

function shuffle(arr) { 
    var shuffled = arr.slice(0), i = arr.length, temp, index; 
    while (i--) { 
     index = Math.floor(i * Math.random()); 
     temp = shuffled[index]; 
     shuffled[index] = shuffled[i]; 
     shuffled[i] = temp; 
    } 
    return shuffled; 
} 

// Create the array 
var i = 1000, arr = []; 
while (i--) arr[i] = i; 

// Shuffle it 
arr = shuffle(arr); 

Answer 5

Лучший способ, вероятно, будет генерировать массив чисел, затем перетасовать его с помощью Fisher-Yates shuffle.

Вот пример JavaScript приведен в статье Википедии: (. Это предполагает, у вас есть массив «а», который содержит элементы, которые вы хотите, чтобы перетасовать)

var n = a.length; 
for(var i = n - 1; i > 0; i--) { 
    var j = Math.floor(Math.random() * (i + 1)); 
    var tmp = a[i]; 
    a[i] = a[j]; 
    a[j] = tmp; 
}