Générer un nombre unique dans la plage (0 – X), garder un historique pour éviter les doublons

Vous avez une excellente réponse à la programmation. Voici un avec une saveur plus théorique pour compléter votre panorama 🙂

Votre problème est appelé «échantillonnage» ou «échantillonnage de sous-ensemble» et il existe plusieurs façons de le faire. Soit N la plage que vous êtes le cadre d'échantillonnage (c'est-à-dire N=X+1 ) et M soit la taille de votre échantillon (le nombre d'éléments que vous souhaitez choisir).

• Si N est beaucoup plus grand que M , vous voudrez utiliser un algorithme tel que celui suggéré par Bentley et Floyd dans sa colonne " Programmer des perles: un échantillon de brillance " (disponible temporairement sans l'écran de verrouillage d'ACM ici ), je recommande vraiment Ceci comme ils donnent explicitement le code et discutent en termes de tables de hash, etc .; Il y a quelques astuces

• Si N est dans la même plage que M , alors vous voudrez peut-être utiliser le shuffle de Fisher-Yates mais arrêtez-vous après seulement M étapes (au lieu de N )

• Si vous ne le savez pas vraiment, l'algorithme de la page 647 du livre de Devroye sur la génération aléatoire est assez rapide .

Cela devrait le faire:

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

Usage:

 var generate = makeRandomRange(20); var x1 = generate(), x2 = generate(), ... 

Bien que cela fonctionne, il n'a pas de bonne performance lorsque le x-th random est généré – il recherche toute la liste pour un endroit libre. Cet algorithme , étape par étape, Fisher-Yates shuffle , à partir de la question des nombres aléatoires uniques (non répétitifs) dans O (1)? , Sera meilleur:

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

( Démo à jsfiddle.net )

Version étendue qui ne génère qu'un "groupe" de nombres uniques:

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

( Demo )

J'ai écrit cette fonction. Il conserve son propre tableau avec une histoire de nombres générés, en empêchant les doublons initiaux, en continuant à produire un nombre aléatoire si tous les nombres de la gamme ont été sortis une fois:

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

Voici un violon de travail

J'espère que cela est utile pour quelqu'un!

Edit: comme indiqué par Pointy ci-dessous, il pourrait ralentir avec une large gamme (voici un violon, passant d'une fourchette de 0-1000 , ce qui semble fonctionner correctement). Toutefois; Je n'avais pas besoin d'une très grande portée, donc peut-être que cette fonction n'est en effet pas adaptée si vous cherchez à générer et à suivre une gamme énorme.

Vous pouvez essayer de générer le numéro à l'aide de la date et de la date actuelles qui le rendraient unique. Pour le faire dans la gamme, vous devrez peut-être utiliser une fonction mathématique.