Уникальный генератор случайных чисел в JavaScript [дубликат]

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

Использовать Переключение Knuth (так называемый Shuffle Fisher-Yates) Алгоритм .

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;

   }
}

CODE COPIED FROM LINK.

EDIT:

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

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.

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

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

Современное решение JS: (и находится в O (n))

const nums = new Set();
while(nums.size !== 8) {
  nums.add(Math.ceil(Math.random() * 100));
}

console.log([...nums]);

Тот же алгоритм перестановки, что и «Charmer Machine», но с прототипированной реализацией. Лучше подходит для большого количества выборков. Использует 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);

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

// 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);

Лучшим более ранним ответом является ответ sje397. Вы получите как можно более хорошие случайные числа, как можно быстрее.

Мое решение очень похоже на его решение. Однако иногда вам нужны случайные числа в случайном порядке, и именно поэтому я решил опубликовать ответ. Кроме того, я предоставляю общую функцию.

function selectKOutOfN(k, n) {
  if (k>n) throw "k>n";
  var selection = [];
  var sorted = [];
  for (var i = 0; i < k; i++) {
    var rand = Math.floor(Math.random()*(n - i));
    for (var j = 0; j < i; j++) {
      if (sorted[j]<=rand)
        rand++;
      else
        break;
    }
    selection.push(rand);
    sorted.splice(j, 0, rand);
  }
  return selection;
}

alert(selectKOutOfN(8, 100));

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

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 как верхний предел случайного числа

Voila - нет повторных чисел.

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

Редактирование: это, вероятно, конкурентная полоса во мне, но, увидев сообщение от @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>

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

Эта функция sample работает лениво, предоставляя вам 1 случайный элемент за итерацию до N предметов, которые вы запрашиваете. Это хорошо, потому что, если вам просто нужно 3 элемента из списка 1000, сначала вам не нужно касаться всех 1000 элементов.

// sample :: Integer -> [a] -> [a]
const sample = n => function* (xs) {
  let ys = xs.slice(0);
  let len = xs.length;
  while (n > 0 && len > 0) {
    let i = (Math.random() * len) >> 0;
    yield ys.splice(i,1)[0];
    n--; len--;
  }
}

// example inputs
let items = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
let numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

// get 3 random items
for (let i of sample(3) (items))
  console.log(i); // f g c

// partial application
const lotto = sample(3);
for (let i of lotto(numbers))
  console.log(i); // 3 8 7

// shuffle an array
const shuffle = xs => Array.from(sample (Infinity) (xs))
console.log(shuffle(items)) // [b c g f d e a]

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

Например, shuffle функция может захотеть изменить исходный массив ввода. Или вы можете попробовать с одного и того же входа в разное время, каждый раз обновляя вход.

// sample :: Integer -> [a] -> [a]
const sample = n => function* (xs) {
  let len = xs.length;
  while (n > 0 && len > 0) {
    let i = (Math.random() * len) >> 0;
    yield xs.splice(i,1)[0];
    n--; len--;
  }
}

// deal :: [Card] -> [Card]
const deal = xs => Array.from(sample (2) (xs));

// setup a deck of cards (13 in this case)
// cards :: [Card]
let cards = 'A234567890JQK'.split('');

// deal 6 players 2 cards each
// players :: [[Card]]
let players = Array.from(Array(6), $=> deal(cards))

console.log(players);
// [K, J], [6, 0], [2, 8], [Q, 7], [5, 4], [9, A]

// `cards` has been mutated. only 1 card remains in the deck
console.log(cards);
// [3]

sample больше не чистая функция из-за входной мутации массива, но в определенных обстоятельствах (продемонстрировано выше) это может иметь больше смысла.

---

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

Возможно, я хочу, чтобы первое простое число из списка из 1 000 000 случайных чисел.

• «Сколько должен ли я пробовать? » - вам не нужно указывать
• « Должен ли я сначала найти все простые числа, а затем выбрать случайное число? » - Нет.

Поскольку мы работаем с генератором, эта задача тривиальна

const randomPrimeNumber = listOfNumbers => {
  for (let x of sample(Infinity) (listOfNumbers)) {
    if (isPrime(x))
      return x;
  }
  return NaN;
}

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

---

Примечание:

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

var bombout=0;
var checkArr=[];
var arr=[];
while(arr.length < 8 && bombout<100){
  bombout++;
  var randomNumber=Math.ceil(Math.random()*100);
  if(typeof checkArr[randomNumber] == "undefined"){
    checkArr[randomNumber]=1;
    arr.push(randomNumber);
  }
}​

// untested - hence bombout

Это мое личное решение:

<script>

var i, k;
var numbers = new Array();
k = Math.floor((Math.random()*8));
numbers[0]=k;
    for (var j=1;j<8;j++){
        k = Math.floor((Math.random()*8));
i=0;
while (i < numbers.length){
if (numbers[i] == k){
    k = Math.floor((Math.random()*8));
    i=0;
}else {i++;}
}
numbers[j]=k;
    }
    for (var j=0;j<8;j++){
alert (numbers[j]);
    }
</script>

Произвольно генерирует 8 уникальных значений массива (от 0 до 7), а затем отображает их с помощью окна предупреждения.

var arr = []
while(arr.length < 8){
  var randomnumber=Math.ceil(Math.random()*100)
  if(arr.indexOf(randomnumber) === -1){arr.push(randomnumber)}  
}
document.write(arr);

короче, чем другие ответы, которые я видел

Я бы сделал это:

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;

Как насчет использования свойств объекта в качестве хеш-таблицы ? Таким образом, ваш лучший сценарий состоит только в случайном 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;
  }
}

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

/* Creates an array of random integers between the range specified 
     len = length of the array you want to generate
     min = min value you require
     max = max value you require
     unique = whether you want unique or not (assume 'true' for this answer)
*/
    function _arrayRandom(len, min, max, unique) {
        var len = (len) ? len : 10,
                min = (min !== undefined) ? min : 1,
                max = (max !== undefined) ? max : 100,
                unique = (unique) ? unique : false,
                toReturn = [], tempObj = {}, i = 0;

        if(unique === true) {
            for(; i < len; i++) {
                var randomInt = Math.floor(Math.random() * ((max - min) + min));
                if(tempObj['key_'+ randomInt] === undefined) {
                    tempObj['key_'+ randomInt] = randomInt;
                    toReturn.push(randomInt);
                } else {
                    i--;
                }
            }
        } else {
            for(; i < len; i++) {
                toReturn.push(Math.floor(Math.random() * ((max - min) + min)));
            }
        }

        return toReturn;
    }

Здесь «tempObj» является очень полезным obj, поскольку каждое генерируемое случайное число будет напрямую проверять этот tempObj, если этот ключ уже существует , если нет, то мы уменьшаем i на единицу, так как нам нужен один дополнительный прогон, так как текущее случайное число уже существует.

В вашем случае запустите следующий

_arrayRandom(8, 1, 100, true);

. Это все.

function getUniqueRandomNos() {
    var indexedArrayOfRandomNo = [];
    for (var i = 0; i < 100; i++) {
        var randNo = Math.random();
        indexedArrayOfRandomNo.push([i, randNo]);
    }
    indexedArrayOfRandomNo.sort(function (arr1, arr2) {
        return arr1[1] - arr2[1]
    });
    var uniqueRandNoArray = [];
    for (i = 0; i < 8; i++) {
        uniqueRandNoArray.push(indexedArrayOfRandomNo[i][0]);
    }
    return uniqueRandNoArray;
}

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

, если вам нужно больше уникального, вы должны сгенерировать массив (1..100).

var arr=[];
function generateRandoms(){
for(var i=1;i<=100;i++) arr.push(i);
}
function extractUniqueRandom()
{
   if (arr.length==0) generateRandoms();
   var randIndex=Math.floor(arr.length*Math.random());
   var result=arr[randIndex];
   arr.splice(randIndex,1);
   return result;

}
function extractUniqueRandomArray(n)
{
   var resultArr=[];
   for(var i=0;i<n;i++) resultArr.push(extractUniqueRandom());
   return resultArr;
}

выше код быстрее: extractUniqueRandomArray (50) => [2, 79, 38, 59, 63, 42, 52, 22, 78, 50, 39, 77, 1, 88, 40, 23, 48, 84, 91, 49, 4, 54, 93, 36, 100, 82, 62, 41, 89, 12, 24, 31, 86, 92, 64, 75, 70, 61, 67, 98, 76, 80, 56, 90, 83, 44, 43, 47, 7, 53]

Вы также можете сделать это с одним слоем следующим образом:

[...((add, set) => add(set, add))((set, add) => set.size < 8 ? add(set.add(Math.floor(Math.random()*100) + 1), add) : set, new Set())]

для массивов с такими отверстиями [,2,,4,,6,7,,], потому что моя проблема заключалась в заполнении этих отверстий. Поэтому я изменил его в соответствии с моей потребностью:)

для меня работало следующее модифицированное решение:)

var arr = [,2,,4,,6,7,,]; //example
while(arr.length < 9){
  var randomnumber=Math.floor(Math.random()*9+1);
  var found=false;
  for(var i=0;i<arr.length;i++){
    if(arr[i]==randomnumber){found=true;break;}
  }

  if(!found)
    for(k=0;k<9;k++)
    {if(!arr[k]) //if it's empty  !!MODIFICATION
      {arr[k]=randomnumber; break;}}
}

alert(arr); //outputs on the screen

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

function randomNumbers() {
  const numbers = [ ...Array(100).keys() ].map(num => num + 1);
  numbers.sort(() => Math.random() - 0.5);
  return numbers.slice(0, 8);
}

Это может обрабатывать генерацию до 20-значного UNIQUE случайного числа

JS

 var generatedNumbers = [];

    function generateRandomNumber(precision) { // input --> number precision in integer 
        if (precision <= 20) {
            var randomNum = Math.round(Math.random().toFixed(precision) * Math.pow(10, precision));
            if (generatedNumbers.indexOf(randomNum) > -1) {
                if (generatedNumbers.length == Math.pow(10, precision))
                    return "Generated all values with this precision";
                    return generateRandomNumber(precision);
            } else {
                generatedNumbers.push(randomNum);
                return randomNum;
            }
        } else
           return "Number Precision shoould not exceed 20";
    }
    generateRandomNumber(1);

jsFiddle

getRandom (min, max) {
  return Math.floor(Math.random() * (max - min)) + min
}

getNRandom (min, max, n) {
  const numbers = []
  if (min > max) {
    return new Error('Max is gt min')
  }

  if (min === max) {
    return [min]
  }

  if ((max - min) >= n) {
    while (numbers.length < n) {
      let rand = this.getRandom(min, max + 1)
      if (numbers.indexOf(rand) === -1) {
        numbers.push(rand)
      }
    }
  }

  if ((max - min) < n) {
    for (let i = min; i <= max; i++) {
      numbers.push(i)
    }
  }
  return numbers
}

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

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

Это решение использует хэш, который намного более эффективен O (1), чем проверка, находится ли он в массиве. Он также имеет дополнительные безопасные проверки. Надеюсь, что это поможет.

function uniqueArray(minRange, maxRange, arrayLength) {
  var arrayLength = (arrayLength) ? arrayLength : 10
  var minRange = (minRange !== undefined) ? minRange : 1
  var maxRange = (maxRange !== undefined) ? maxRange : 100
  var numberOfItemsInArray = 0
  var hash = {}
  var array = []

  if ( arrayLength > (maxRange - minRange) ) throw new Error('Cannot generate unique array: Array length too high')

  while(numberOfItemsInArray < arrayLength){
    // var randomNumber = Math.floor(Math.random() * (maxRange - minRange + 1) + minRange)
    // following line used for performance benefits
    var randomNumber = (Math.random() * (maxRange - minRange + 1) + minRange) << 0

    if (!hash[randomNumber]) {
      hash[randomNumber] = true
      array.push(randomNumber)
      numberOfItemsInArray++
    }
  }
  return array
}
document.write(uniqueArray(1, 100, 8))

Добавление другой лучшей версии того же кода (принятый ответ) с помощью функции JavaScript 1.6 indexOf.

var arr = []
while(arr.length < 8){
  var randomnumber=Math.ceil(Math.random()*100)
  var found=false;
    if(arr.indexOf(randomnumber) > -1){found=true;}
  if(!found)arr[arr.length]=randomnumber;
}

Старая версия Javascript все еще может использовать версию сверху

PS: Пробовал предлагать обновление к вики, но он был отклонен. Я все еще думаю, что это может быть полезно для других.

Использование Set - ваш самый быстрый вариант. Вот общая функция для получения уникального случайного, использующего генератор обратного вызова. Теперь он быстрый и многоразовый.

// Get a unique 'anything'
let unique = new Set()

function getUnique(generator) {
  let number = generator()
  while (!unique.add(number)) {
    number = generator()
  }
  return number;
}

// The generator.  Return anything, not just numbers.
const between_1_100 = () => 1 + Math.floor(Math.random() * 100)

// Test it
for (var i = 0; i < 8; i++) {
  const aNumber = getUnique(between_1_100)
}
// Dump the 'stored numbers'
console.log(Array.from(unique))

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

В частности, для решения вашего вопроса, используя Chance, это так же просто, как:

// One line!
var uniques = chance.unique(chance.natural, 8, {min: 1, max: 100});

// Print it out to the document for this snippet so we can see it in action
document.write(JSON.stringify(uniques));

<script src="http://chancejs.com/chance.min.js"></script>

Отказ от ответственности, as автор Chance, я немного предвзято;)