Генерируйте уникальные случайные числа между 1 и 100

1. Заполните массив числами от 1 до 100.
2. Перемешайте .
3. Возьмите первые 8 элементов результирующего массива.

Тот же алгоритм перестановки, что и в The Machine Charmer, но с прототипированной реализацией. Лучше подходит для большого количества перестановок. Использует js 1.7 деструктурирующее назначение, если доступно.

// swaps elements at index i and j in array this
// swapping is easy on js 1.7 (feature detection)
Array.prototype.swap = (function () {
    var i=0, j=1;
    try { [i,j]=[j,i]; }
    catch (e) {}
    if(i) {
        return function(i,j) {
            [this[i],this[j]] = [this[j],this[i]];
            return this;
        }
    } else {
        return function(i,j) {
            var temp = this[i];
            this[i] = this[j];
            this[j] = temp;
            return this;
        }
    }
})();


// shuffles array this
Array.prototype.shuffle = function() {
    for(var i=this.length; i>1; i--) {
        this.swap(i-1, Math.floor(i*Math.random()));
    }
    return this;
}

// returns n unique random numbers between min and max
function pick(n, min, max) {
    var a = [], i = max;
    while(i >= min) a.push(i--);
    return a.shuffle().slice(0,n);
}

pick(8,1,100);

Edit: Другое предложение, лучше подходящее для небольшого числа подборов, основанное на ответе belugabob. Чтобы гарантировать уникальность, мы удаляем выбранные числа из массива.

// removes n random elements from array this
// and returns them
Array.prototype.pick = function(n) {
    if(!n || !this.length) return [];
    var i = Math.floor(this.length*Math.random());
    return this.splice(i,1).concat(this.pick(n-1));
}

// returns n unique random numbers between min and max
function pick(n, min, max) {
    var a = [], i = max;
    while(i >= min) a.push(i--);
    return a.pick(n);
}

pick(8,1,100);

Как насчет использования свойств объекта в качестве хеш-таблицы ? Таким образом, ваш лучший сценарий - рандомизировать только 8 раз. Это будет эффективно только в том случае, если вам нужна небольшая часть диапазона чисел.Это также намного менее интенсивно использует память, чем Fisher-Yates, потому что вам не нужно выделять пространство для массива.

var ht={}, i=rands=8;
while ( i>0 || keys(ht).length<rands) ht[Math.ceil(Math.random()*100)]=i--;
alert(keys(ht));

Затем я обнаружил, что Object.keys (obj) - это функция ECMAScript 5, поэтому в настоящее время все вышесказанное бесполезно в Интернете. Не бойтесь, потому что я сделал его совместимым с ECMAScript 3, добавив такую ​​функцию клавиш.

if (typeof keys == "undefined") 
{ 
  var keys = function(obj) 
  {
    props=[];
    for (k in ht) if (ht.hasOwnProperty(k)) props.push(k);
    return props;
  }
}

Перетасовка чисел от 1 до 100 - правильная базовая стратегия, но если вам нужно только 8 перемешанных чисел, нет необходимости перемешивать все 100 номеров.

Я не очень хорошо знаю Javascript, но считаю, что быстро создать массив из 100 нулей легко.Затем в течение 8 раундов вы меняете местами n-й элемент массива (n начиная с 0) на случайно выбранный элемент от n + 1 до 99. Конечно, любые элементы, которые еще не заполнены, означают, что элемент действительно был исходный индекс плюс 1, так что это тривиально для учета. Когда вы закончите с 8 раундами, первые 8 элементов вашего массива будут иметь ваши 8 перемешанных чисел.

Я бы сделал так:

function randomInt(min, max) {
    return Math.round(min + Math.random()*(max-min));
}
var index = {}, numbers = [];
for (var i=0; i<8; ++i) {
    var number;
    do {
        number = randomInt(1, 100);
    } while (index.hasOwnProperty("_"+number));
    index["_"+number] = true;
    numbers.push(number);
}
delete index;

Сгенерируйте перестановку из 100 номеров, а затем выберите последовательно.

Используйте алгоритм Knuth Shuffle (он же Fisher-Yates shuffle) .

JavaScript:

  function fisherYates ( myArray,stop_count ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  int c = 0;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;

     // Edited thanks to Frerich Raabe
     c++;
     if(c == stop_count)return;

   }
}

КОД, КОПИРОВАННЫЙ СО ССЫЛКИ.

РЕДАКТИРОВАТЬ :

Улучшенный код:

function fisherYates(myArray,nb_picks)
{
    for (i = myArray.length-1; i > 1  ; i--)
    {
        var r = Math.floor(Math.random()*i);
        var t = myArray[i];
        myArray[i] = myArray[r];
        myArray[r] = t;
    }

    return myArray.slice(0,nb_picks);
}

Возможная проблема:

Предположим, у нас есть массив из 100 чисел {например, [1,2,3 ... 100]} и мы прекращаем замену после 8 замен; тогда массив в большинстве случаев будет выглядеть как {1,2,3,76,5,6,7,8 , ... номера здесь перетасуются ... 10}.

Поскольку каждое число будет переставлено местами с вероятностью 1/100, поэтому проб. замены первых 8 номеров составляет 8/100, тогда как вероятность. из подкачки других 92 это 92/100.

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

В противном случае мы столкнемся с вопросом: какие 8 чисел выбрать?

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

1. Генерируем массив, содержащий числа от 1 до 100, по порядку.
2. Генерируем случайное число от 1 до 100
3. Ищем число по данному индексу в массиве и сохраняем в результатах
4. Удаляем этот элемент из массива, делая его на один короче
5. Повторяем шаг 2, но используем 99 как верхний предел случайного числа
6. Повторяем шаг 2, но используем 98 как верхний предел случайного числа
7. Повторяем шаг 2, но используйте 97 в качестве верхнего предела случайного числа
8. Повторите шаг 2, но используйте 96 в качестве верхнего предела случайного числа
9. Повторите шаг 2, но используйте 95 в качестве верхнего предела случайного числа
10. Повторите шаг 2, но используйте 94 в качестве верхнего предела случайного числа
11. Повторите шаг 2, но используйте 93 в качестве верхнего предела случайного числа

Вуаля - нет повторяющихся чисел.

Я могу выложить некоторый фактический код позже, если кому-то интересно.

Edit: Возможно, во мне говорит соревновательная жилка, но, увидев сообщение @Alsciende, я не смог удержаться и выложил обещанный код.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html>
<head>
<title>8 unique random number between 1 and 100</title>
<script type="text/javascript" language="Javascript">
    function pick(n, min, max){
        var values = [], i = max;
        while(i >= min) values.push(i--);
        var results = [];
        var maxIndex = max;
        for(i=1; i <= n; i++){
            maxIndex--;
            var index = Math.floor(maxIndex * Math.random());
            results.push(values[index]);
            values[index] = values[maxIndex];
        }
        return results;
    }
    function go(){
        var running = true;
        do{
            if(!confirm(pick(8, 1, 100).sort(function(a,b){return a - b;}))){
                running = false;
            }
        }while(running)
    }
</script>
</head>

<body>
    <h1>8 unique random number between 1 and 100</h1>
    <p><button onclick="go()">Click me</button> to start generating numbers.</p>
    <p>When the numbers appear, click OK to generate another set, or Cancel to stop.</p>
</body>