La création de nombres aléatoires avec pas de doublons

La façon la plus simple serait de créer une liste de nombres (1..20 ou quoi que ce soit), puis les mélanger avec Collections.shuffle. Puis il suffit de prendre toutefois de nombreux éléments que vous voulez. C'est très bien si votre portée est égale au nombre d'éléments dont vous avez besoin à la fin (par exemple, pour traînant un jeu de cartes).

Qui ne fonctionne pas tellement bien si vous voulez (par exemple) 10 éléments aléatoires dans l'intervalle 1..10,000 - vous finirais par faire beaucoup de travail inutilement. À ce stade, il est probablement préférable de garder un ensemble de valeurs que vous avez généré jusqu'à présent, et juste continuer à générer des nombres dans une boucle jusqu'à ce que le prochain n'est pas déjà présent:

if (max < numbersNeeded)
{
    throw new IllegalArgumentException("Can't ask for more numbers than are available");
}
Random rng = new Random(); //Ideally just create one instance globally
//Note: use LinkedHashSet to maintain insertion order
Set<Integer> generated = new LinkedHashSet<Integer>();
while (generated.size() < numbersNeeded)
{
    Integer next = rng.nextInt(max) + 1;
    //As we're adding to a set, this will automatically do a containment check
    generated.add(next);
}

Être prudent avec le choix même si j'ai très délibérément utilisé LinkedHashSet car il maintient l'ordre d'insertion, ce qui nous intéresse ici, c'.

Encore une autre option est de toujours faire des progrès, par la réduction de la gamme de chaque temps et de compensation pour les valeurs existantes. Ainsi, par exemple, supposons que vous vouliez 3 valeurs dans l'intervalle 0..9. Sur la première itération, vous auriez générer un nombre dans l'intervalle 0..9 - disons que vous générez un 4.

Sur la deuxième itération vous pouvez générer un nombre dans l'intervalle 0..8. Si le nombre généré est inférieur à 4, vous garderais comme ça... sinon, vous ajoutez une. Qui vous obtient un résultat de 0..9 sans 4. Supposons que nous obtenons 7 de cette façon.

Sur la troisième itération, vous auriez générer un nombre dans l'intervalle 0..7. Si le nombre généré est inférieur à 4, vous auriez du garder comme ça. Si c'est 4 ou 5, vous devez ajouter un. Si c'est 6 ou 7, vous devez ajouter deux. De cette façon, le résultat varie de 0..9 sans 4 ou 6.

//random numbers are 0,1,2,3 
ArrayList<Integer> numbers = new ArrayList<Integer>();   
Random randomGenerator = new Random();
while (numbers.size() < 4) {

    int random = randomGenerator .nextInt(4);
    if (!numbers.contains(random)) {
        numbers.add(random);
    }
}

Il y a une autre façon de faire "aléatoire" ordonné des nombres avec LFSR, jetez un oeil à:

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

avec cette technique, vous pouvez obtenir l'ordonnée de nombres aléatoires par index et faire en sorte que les valeurs ne sont pas dupliqués.

Mais ce ne sont pas de VRAIS nombres aléatoires, parce que la génération aléatoire est déterministe.

Mais en fonction de votre cas vous pouvez utiliser cette technique réduisant la quantité de traitement sur la génération de nombre aléatoire lors de l'utilisation de brassage.

Ici un LFSR de l'algorithme en java, (je l'ai pris quelque part je n'ai pas l'oublier):

public final class LFSR {
private static final int M = 15;
//hard-coded for 15-bits
private static final int[] TAPS = {14, 15};
private final boolean[] bits = new boolean[M + 1];
public LFSR() {
this((int)System.currentTimeMillis());
}
public LFSR(int seed) {
for(int i = 0; i < M; i++) {
bits[i] = (((1 << i) & seed) >>> i) == 1;
}
}
/* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
public short nextShort() {
//printBits();
//calculate the integer value from the registers
short next = 0;
for(int i = 0; i < M; i++) {
next |= (bits[i] ? 1 : 0) << i;
}
//allow for zero without allowing for -2^31
if (next < 0) next++;
//calculate the last register from all the preceding
bits[M] = false;
for(int i = 0; i < TAPS.length; i++) {
bits[M] ^= bits[M - TAPS[i]];
}
//shift all the registers
for(int i = 0; i < M; i++) {
bits[i] = bits[i + 1];
}
return next;
}
/** returns random double uniformly over [0, 1) */
public double nextDouble() {
return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
}
/** returns random boolean */
public boolean nextBoolean() {
return nextShort() >= 0;
}
public void printBits() {
System.out.print(bits[M] ? 1 : 0);
System.out.print(" -> ");
for(int i = M - 1; i >= 0; i--) {
System.out.print(bits[i] ? 1 : 0);
}
System.out.println();
}
public static void main(String[] args) {
LFSR rng = new LFSR();
Vector<Short> vec = new Vector<Short>();
for(int i = 0; i <= 32766; i++) {
short next = rng.nextShort();
//just testing/asserting to make 
//sure the number doesn't repeat on a given list
if (vec.contains(next))
throw new RuntimeException("Index repeat: " + i);
vec.add(next);
System.out.println(next);
}
}
}

De générer tous les indices d'une séquence est généralement une mauvaise idée, car cela peut prendre beaucoup de temps, surtout si le rapport entre le nombre d'être choisis pour MAX est faible (la complexité devient dominé par O(MAX)). Cela devient pire si le rapport entre le nombre d'être choisis pour MAX approches, comme le retrait d'choisi indices à partir de la séquence de tous les devient aussi cher (nous avons une approche O(MAX^2/2)). Mais pour les petits nombres, ce qui en général fonctionne bien et n'est pas particulièrement enclin à l'erreur.

De filtrage de l'généré indices en utilisant une collection, c'est aussi une mauvaise idée, car peu de temps est consacré à l'insertion de l'index dans la séquence, et le progrès n'est pas garanti que le même nombre aléatoire peut être tirée en plusieurs fois (mais assez grande pour MAX c'est peu probable). Cela pourrait être proche de la complexité
O(k n log^2(n)/2), en ignorant les doublons et en supposant que la collection utilise un arbre pour faciliter la recherche (mais avec un important coût constant k de l'allocation de l'arbre de nœuds, et après avoir éventuellement à rééquilibrer).

Une autre option est de générer des valeurs aléatoires de manière unique à partir du début, en garantissant des progrès sont réalisés. Cela signifie que dans le premier tour, un hasard index dans [0, MAX] est généré:

items i0 i1 i2 i3 i4 i5 i6 (total 7 items)
idx 0       ^^             (index 2)

Dans le deuxième tour, seulement [0, MAX - 1] est généré (comme un seul élément est sélectionné):

items i0 i1    i3 i4 i5 i6 (total 6 items)
idx 1          ^^          (index 2 out of these 6, but 3 out of the original 7)

Les valeurs des indices doivent ensuite être ajusté: si l'index du deuxième tombe dans la seconde moitié de la séquence (après le premier index), il doit être augmenté pour tenir compte de l'écart. Nous pouvons mettre en œuvre la présente comme une boucle, ce qui nous permet de sélectionner nombre arbitraire d'objets uniques.

Pour de courtes séquences, c'est assez rapide O(n^2/2) algorithme:

void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); //!!
//b1: 3187.000 msec (the fastest)
//b2: 3734.000 msec
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
//get a random number
size_t n_where = i;
for(size_t j = 0; j < i; ++ j) {
if(n + j < rand_num[j]) {
n_where = j;
break;
}
}
//see where it should be inserted
rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
//insert it in the list, maintain a sorted sequence
}
//tier 1 - use comparison with offset instead of increment
}

Où n_select_num est votre 5 et n_number_num est votre MAX. Le n_Rand(x) retourne entiers aléatoires dans [0, x] (inclus). Cela peut être fait en un peu plus rapide si la sélection d'un grand nombre d'éléments (par exemple, pas 5, mais 500) à l'aide de binaires de recherche pour trouver le point d'insertion. Pour ce faire, nous devons nous assurer que nous remplissons les exigences.

Nous ferons de recherche binaire avec la comparaison n + j < rand_num[j] qui est le même que
n < rand_num[j] - j. Nous avons besoin de montrer que rand_num[j] - j est encore une séquence ordonnée pour une séquence triée rand_num[j]. C'est heureusement facilement montré, comme étant la plus petite distance entre deux éléments de l'original rand_num est l'un (les nombres générés sont uniques, il y a toujours une différence d'au moins 1). En même temps, si on soustrait les indices j de tous les éléments
rand_num[j], les différences dans l'indice sont exactement 1. Ainsi, dans le "pire" des cas, nous obtenons une constante de la séquence, mais jamais à la baisse. Le binaire de recherche peut donc être utilisé, produisant O(n log(n)) algorithme:

struct TNeedle { //in the comparison operator we need to make clear which argument is the needle and which is already in the list; we do that using the type system.
int n;
TNeedle(int _n)
:n(_n)
{}
};
class CCompareWithOffset { //custom comparison "n < rand_num[j] - j"
protected:
std::vector<int>::iterator m_p_begin_it;
public:
CCompareWithOffset(std::vector<int>::iterator p_begin_it)
:m_p_begin_it(p_begin_it)
{}
bool operator ()(const int &r_value, TNeedle n) const
{
size_t n_index = &r_value - &*m_p_begin_it;
//calculate index in the array
return r_value < n.n + n_index; //or r_value - n_index < n.n
}
bool operator ()(TNeedle n, const int &r_value) const
{
size_t n_index = &r_value - &*m_p_begin_it;
//calculate index in the array
return n.n + n_index < r_value; //or n.n < r_value - n_index
}
};

Et enfin:

void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); //!!
//b1: 3578.000 msec
//b2: 1703.000 msec (the fastest)
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
//get a random number
std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
TNeedle(n), CCompareWithOffset(rand_num.begin()));
//see where it should be inserted
rand_num.insert(p_where_it, 1, n + p_where_it - rand_num.begin());
//insert it in the list, maintain a sorted sequence
}
//tier 4 - use binary search
}

J'ai testé cela sur trois repères. Tout d'abord, les 3 numéros ont été choisis de 7 éléments, et un histogramme des éléments choisis a accumulé plus de 10 000 pistes:

4265 4229 4351 4267 4267 4364 4257

Cela montre que chacun des 7 éléments a été choisi à peu près le même nombre de fois, et il n'est pas évident biais causé par l'algorithme. Toutes les séquences ont été également vérifié l'exactitude de l' (unicité de contenu).

Le deuxième point de référence consistait à choisir 7 numéros de 5000 articles. Le temps de plusieurs versions de l'algorithme a été accumulé plus de 10 000 000 pistes. Les résultats sont indiqués dans les commentaires dans le code b1. La version simple de l'algorithme est un peu plus rapide.

Le troisième test consistait à choisir 700 numéros de 5000 articles. Le temps de plusieurs versions de l'algorithme a été créée, cette fois, plus de 10 000 pistes. Les résultats sont indiqués dans les commentaires dans le code b2. La recherche binaire version de l'algorithme est maintenant plus que deux fois plus rapide que la simple.

La deuxième méthode commence à être plus rapide pour le choix plus que la dpa 75 articles sur ma machine (à noter que la complexité de l'algorithme ne dépend pas du nombre d'éléments, MAX).

Il est à noter que les algorithmes ci-dessus générer des nombres aléatoires dans l'ordre croissant. Mais il serait simple d'ajouter un autre tableau dont les chiffres seront enregistrées dans l'ordre dans lequel ils ont été générés, et de retour à la place (à négligeable des coûts supplémentaires O(n)). Il n'est pas nécessaire de mélanger la sortie: ce serait beaucoup plus lent.

Noter que les sources sont en C++, je n'ai pas de Java sur ma machine, mais le concept doit être clair.

MODIFIER:

Pour l'amusement, j'ai également mis en œuvre l'approche qui génère une liste avec tous les indices
0 .. MAX, choisit au hasard et les supprime de la liste pour garantir l'unicité. Depuis que j'ai choisi assez élevé MAX (5000), le rendement est catastrophique:

//b1: 519515.000 msec
//b2: 20312.000 msec
std::vector<int> all_numbers(n_item_num);
std::iota(all_numbers.begin(), all_numbers.end(), 0);
//generate all the numbers
for(size_t i = 0; i < n_number_num; ++ i) {
assert(all_numbers.size() == n_item_num - i);
int n = n_Rand(n_item_num - i - 1);
//get a random number
rand_num.push_back(all_numbers[n]); //put it in the output list
all_numbers.erase(all_numbers.begin() + n); //erase it from the input
}
//generate random numbers

J'ai également mis en œuvre l'approche avec un set (C++ collection), ce qui en fait vient en seconde place sur le benchmark b2, étant seulement environ 50% plus lent que l'approche avec le binaire de recherche. C'est compréhensible, que le set utilise un arbre binaire, où le coût d'insertion est similaire à la recherche binaire. La seule différence est la possibilité d'obtenir des articles en double, ce qui ralentit la progression.

//b1: 20250.000 msec
//b2: 2296.000 msec
std::set<int> numbers;
while(numbers.size() < n_number_num)
numbers.insert(n_Rand(n_item_num - 1)); //might have duplicates here
//generate unique random numbers
rand_num.resize(numbers.size());
std::copy(numbers.begin(), numbers.end(), rand_num.begin());
//copy the numbers from a set to a vector

L'intégralité du code source est ici.

Plutôt que de faire tout cela créer un LinkedHashSet objet et de nombres aléatoires par Math.random() fonction .... si aucune entrée dupliquée se produit le LinkedHashSet objet de ne pas ajouter ce numéro à la Liste ... Car dans cette Collection, la Classe pas de doublons sont autorisés .. en fin de compte u obtenir une liste de nombres aléatoires ayant pas de valeurs dupliquées .... 😀

Ce serait beaucoup plus simple dans java-8:

Stream.generate(new Random()::ints)
.distinct()
.limit(16) //whatever limit you might need
.toArray(Integer[]::new);

Ici est une solution efficace pour la création rapide d'un essai randomisé de tableau. Après randomisation, vous pouvez simplement choisir le n-ème élément e de la matrice, incrément n et retour e. Cette solution a O(1) pour obtenir un nombre aléatoire et O(n) pour l'initialisation, mais comme un compromis nécessite une bonne quantité de mémoire si n devient assez grand.

Elle a vraiment tout dépend exactement CE que vous avez besoin de la génération aléatoire, mais voici mon point de vue.

Tout d'abord, créez un autonome méthode pour générer le nombre aléatoire.
Assurez-vous de permettre à des limites.

public static int newRandom(int limit){
return generatedRandom.nextInt(limit);  }

Ensuite, vous voulez pour créer une très simple structure de décision qui compare les valeurs. Cela peut être fait de deux façons. Si vous avez une quantité très limitée de numéros de vérifier, d'une SI simple déclaration suffira:

public static int testDuplicates(int int1, int int2, int int3, int int4, int int5){
boolean loopFlag = true;
while(loopFlag == true){
if(int1 == int2 || int1 == int3 || int1 == int4 || int1 == int5 || int1 == 0){
int1 = newRandom(75);
loopFlag = true;    }
else{
loopFlag = false;   }}
return int1;    }

Ci-dessus compare int1 à int2 par int5, ainsi que de s'assurer qu'il n'y a pas de zéros dans les randoms.

Avec ces deux méthodes, nous pouvons effectuer les opérations suivantes:

    num1 = newRandom(limit1);
num2 = newRandom(limit1);
num3 = newRandom(limit1);
num4 = newRandom(limit1);
num5 = newRandom(limit1);

Suivie Par:

        num1 = testDuplicates(num1, num2, num3, num4, num5);
num2 = testDuplicates(num2, num1, num3, num4, num5);
num3 = testDuplicates(num3, num1, num2, num4, num5);
num4 = testDuplicates(num4, num1, num2, num3, num5);
num5 = testDuplicates(num5, num1, num2, num3, num5);

Si vous avez une longue liste pour vérifier, puis une méthode plus complexe d'obtenir de meilleurs résultats à la fois dans la clarté du code et des ressources de traitement.

Espère que cette aide. Ce site m'a beaucoup aidée, je me suis senti obligé pour au moins ESSAYER de nous aider.