Как бы вы не допустили, чтобы Math.random () в javascript выбирал одни и те же числа несколько раз?

Question

У меня есть массив var words = []//lots of different words in it.У меня есть Math.floor(Math.random()*words.length), который выбирает случайное слово из массива.Это выполняется в цикле, который выполняется случайное количество раз (от 2 до 200 раз).Я хотел бы убедиться, что случайные числа выбираются не более одного раза за время выполнения цикла.Как бы вы предложили это сделать?

Answer 1

Есть несколько способов сделать это.

Вы можете перетасовать всю коллекцию и просто брать предметы с одного конца. Это гарантирует, что вы не встретите ни одного элемента более одного раза (точнее, больше, чем количество раз, которое оно встречалось в исходном входном массиве) за одну целую итерацию.

Однако для этого необходимо либо изменить оригинальную коллекцию на месте, либо создать ее копию.

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

Вы можете использовать хеш-таблицу или другой тип словаря и просто проверить, существует ли элемент, выбранный случайным образом в исходной коллекции, в словаре. Если это не так, добавьте его в словарь и используйте его. Если он уже существует в словаре, выберите снова.

Этот подход использует хранилище, пропорциональное количеству предметов, которые вам нужно выбрать.

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

Answer 2

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

a = "abcdefghijklmnopq".split("");
c = 0;
r = [];

do {
   var len = a.length - c;
   var rnd = Math.floor(Math.random() * len);
   r.push(a[rnd]);
   a[rnd] = a[len - 1];
} while(++c < 5);

console.log(r);

идея состоит в том, чтобы выбрать из 0..(length - step) элементов, а затем сдвинуть выбранный элемент к концу.

Answer 3

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

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;
}

console.log(shuffle(["one", "two", "three", "four"]));

Answer 4

Существует несколько различных подходов, которые более или менее эффективны в зависимости от того, сколько у вас данных и сколько элементов вы хотите выбрать:

• Удалить элементы из массива, как только они былиselected.
• Перемешать массив и получить первые элементы.
• Хранить список выбранных элементов и сравнивать их с новыми выборками.
• Перебирать элементы и выбирать значения случайным образом на основена вероятность быть выбранным.

Answer 5

Я бы попробовал использовать карту (Object литерал) вместо Array с ключами, являющимися индексами:

var words = [ /* ... */ ] , map = { } , length = words.length ;
for(var n = 0 ; n < length ; n++) map[n] = words[n] ;

затем создайте функцию для выбора случайной записи на основе длины, удаления записи (отсюда и индекса) и настройки длины:

function pickRandomEntry() {

    var random = Math.floor( Math.random() * length ) ;

    var entry = map[random] ;

        delete map[random] ;
        length-- ;

    return entry ;

}

при таком подходе вы должны проверить возвращаемое значение undefined (поскольку random может вернуть то же число) и запустить функцию снова, пока она не вернет фактическое значение; или создайте массив выбранных индексов для фильтрации случайных чисел (что, однако, снизит производительность в случае длинных циклов итерации).

НТН

Answer 6

Для этого есть несколько решений.

Что вы можете сделать, это использовать .splice () в вашем массиве, чтобы удалить элемент, пораженный словами.

Затем вы можете выполнить итерациюВаш массив, пока он не пуст.Если вам нужно сохранить исходный массив, вы можете сначала создать его копию и выполнить итерацию по копии.

var words = ['apple', 'banana', 'cocoa', 'dade', 'elephant'];
while (words.length > 0) {
    var i    = Math.floor(Math.random()*words.length);
    var word = words.splice(i, 1)[0];
}

Или что-то на этот счет.

Answer 7

Вот способ с простыми числами и по модулю, который, кажется, делает свое дело без перемещения исходного массива или добавления хэша:

<html>
<head>
</head>
<body>
 <a href="javascript:" onclick="shuffle(['48','49','50','51','52','53','54','55','56','57','58','59','60','61','62','63','64','65','66','67','68','69','70','71','72','73','74','75','76','77','78','79','80','81','82','83','84','85','86','87','88','89','90','91','92','93','94','1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16','17','18','19','20','21','22','23','24','25','26','27','28','29','30','31','32','33','34','35','36','37','38','39','40','41','42','43','44','45','46','47','95','96','97','98','99'])">shuffle</a>
 <div id="res"></div>
 <script>
    function shuffle(words){
        var l = words.length,i = 1,primes = [43,47,53,59,61,67,71,73,79],//add more if needed
        prime = primes[parseInt(Math.random()*primes.length, 10)],
        temp = [];
        do{
            temp.push((i * prime) % l);
        }while(++i <= l);
        console.log(temp.join(','));
        console.log(temp.sort().join(','));
    }
 </script>
</body>
</html>