Nombres aléatoires uniques dans un tableau d’entiers dans le langage de programmation C

Dupliquer possible:
Des nombres aléatoires uniques dans O (1)?

Comment remplir un tableau d’entiers avec des valeurs uniques (pas de doublons) en C?

int vektor[10]; for (i = 0; i < 10; i++) { vektor[i] = rand() % 100 + 1; } //No uniqueness here 

Il existe plusieurs façons de résoudre votre problème. Chacune a ses avantages et ses inconvénients.

Je voudrais d’abord noter que vous avez déjà reçu un certain nombre de réponses qui génèrent les actions suivantes: elles génèrent un nombre aléatoire, puis vérifient si elles ont déjà été utilisées dans le tableau et si elles ont déjà été utilisées, elles en génèrent une autre. nombre jusqu’à ce qu’ils trouvent un non utilisé. C’est une approche naïve et, à vrai dire, gravement défectueuse. Le problème est lié à la nature cyclique de la génération de nombre d’essais par tâtonnements (“s’il est déjà utilisé, essayez à nouveau”). Si la plage numérique (par exemple, [1..N]) est proche de la longueur du tableau souhaité (par exemple, M), alors, à la fin, l’algorithme risque de passer énormément de temps à essayer de trouver le nombre suivant. Si le générateur de nombres aléatoires est même un peu cassé (par exemple, ne génère jamais un nombre, ou le fait très rarement), alors avec N == M, il est garanti que l’algorithme fonctionne en boucle pour toujours (ou pour un temps très long). En règle générale, cette approche empirique est inutile ou, au mieux, imparfaite.

Une autre approche déjà présentée ici consiste à générer une permutation aléatoire dans un tableau de taille N. L’idée de la permutation aléatoire est prometteuse, mais le faire sur un tableau de taille N (lorsque M << N) générera certainement plus de chaleur que de lumière. , parlant figurativement.

Vous trouverez de bonnes solutions à ce problème, par exemple dans “Programming Pearls” de Bentley (certaines d’entre elles sont tirées de Knuth).


  • L’algorithme de Knuth. C’est un algorithme très simple avec une complexité de O (N) (c’est-à-dire la plage numérique), ce qui signifie qu’il est le plus utilisable lorsque M est proche de N. Cependant, cet algorithme ne nécessite aucune mémoire supplémentaire en plus de votre vektor array, par opposition à la variante déjà proposée avec les permutations (ce qui signifie qu’elle prend O (M) en mémoire, et non O (N) comme les autres algorithmes basés sur la permutation suggérés ici). Ce dernier en fait un algorithme viable même pour M << N cas.

L’algorithme fonctionne comme suit: parcourez tous les nombres de 1 à N et sélectionnez le nombre actuel avec une probabilité rm / rn , où rm représente le nombre de nombres que vous devez encore rechercher et rn le nombre de nombres que vous devez encore parcourir. Voici une implémentation possible pour votre cas

 #define M 10 #define N 100 int in, im; im = 0; for (in = 0; in < N && im < M; ++in) { int rn = N - in; int rm = M - im; if (rand() % rn < rm) /* Take it */ vektor[im++] = in + 1; /* +1 since your range begins from 1 */ } assert(im == M); 

Après ce cycle, nous obtenons un tableau vektor rempli de nombres choisis au hasard, par ordre croissant . Le bit "ordre croissant" est ce dont nous n'avons pas besoin ici. Donc, pour "réparer" que nous venons de faire une permutation aléatoire d’éléments de vektor et nous avons terminé. Notez qu'il s'agit d'une permutation O (M) ne nécessitant aucune mémoire supplémentaire. (Je laisse de côté l'implémentation de l'algorithme de permutation. Beaucoup de liens ont déjà été donnés ici.).

Si vous examinez attentivement les algorithmes basés sur la permutation proposés ici qui fonctionnent sur un tableau de longueur N, vous constaterez que la plupart d'entre eux sont à peu près identiques au même algorithme de Knuth, mais reformulés pour M == N Dans ce cas, le cycle de sélection ci-dessus choisira chacun des nombres compris dans la plage [1..N] avec la probabilité 1, ce qui aboutira effectivement à l'initialisation d'un tableau N portant les nombres 1 à N. Compte tenu de cela, je pense que cela devient plutôt Il est évident qu'exécuter cet algorithme pour M == N et ensuite tronquer le résultat (éventuellement en en rejetant la majeure partie) est beaucoup moins logique que de simplement exécuter cet algorithme dans sa forme d'origine pour la valeur d'origine de M et obtenir immédiatement le résultat, sans aucune modification. troncature.


  • L'algorithme de Floyd (voir ici ). Cette approche a la complexité d’environ O (M) (dépend de la structure de recherche utilisée); elle convient donc mieux lorsque M << N. Cette approche garde la trace des nombres aléatoires déjà générés et nécessite donc davantage de mémoire. Cependant, la beauté de cette méthode est qu’elle ne fait aucune de ces abominables itérations d’essais et d’erreur, en essayant de trouver un nombre aléatoire inutilisé. Cet algorithme est garanti pour générer un numéro aléatoire unique après chaque appel au générateur de nombres aléatoires.

Voici une implémentation possible pour votre cas. (Il y a différentes façons de garder une trace des nombres déjà utilisés. Je vais simplement utiliser un tableau de drapeaux, en supposant que N ne soit pas prohibitif.)

 #define M 10 #define N 100 unsigned char is_used[N] = { 0 }; /* flags */ int in, im; im = 0; for (in = N - M; in < N && im < M; ++in) { int r = rand() % (in + 1); /* generate a random number 'r' */ if (is_used[r]) /* we already have 'r' */ r = in; /* use 'in' instead of the generated number */ assert(!is_used[r]); vektor[im++] = r + 1; /* +1 since your range begins from 1 */ is_used[r] = 1; } assert(im == M); 

Pourquoi les travaux ci-dessus ne sont pas immédiatement évidents. Mais ça marche. Exactement M nombres de [1..N] seront choisis avec une dissortingbution uniforme.

Notez que pour les grands N, vous pouvez utiliser une structure basée sur la recherche pour stocker les nombres "déjà utilisés", obtenant ainsi un bel algorithme O (M log M) avec une mémoire requirejse de O (M).

(Cependant, il y a une chose à propos de cet algorithme: bien que le tableau résultant ne soit pas ordonné, une certaine "influence" de l'ordre 1..N d'origine sera toujours présente dans le résultat. Par exemple, il est évident que le nombre N, si sélectionné, ne peut être que le tout dernier membre du tableau résultant. Si cette "contamination" du résultat par un ordre inattendu n'est pas acceptable, le tableau vektor résultant peut être aléatoire, comme dans l'algorithme de Khuth.


Notez le point très critique observé dans la conception de ces deux algorithmes: ils ne font jamais de boucle , essayant de trouver un nouveau nombre aléatoire inutilisé. Tout algorithme qui crée des itérations d’essais et d’erreur avec des nombres aléatoires est défectueux du sharepoint vue pratique. En outre, la consommation de mémoire de ces algorithmes est liée à M, pas à N

Pour l'OP, je recommanderais l'algorithme de Floyd, car dans son application, M semble être considérablement inférieur à N et qu'il ne nécessite pas (ou peut ne pas) nécessiter une passe supplémentaire pour la permutation. Cependant, pour de si petites valeurs de N, la différence pourrait être négligeable.

Dans votre exemple (choisissez 10 nombres aléatoires uniques compris entre 1 et 100), vous pouvez créer une liste avec les nombres compris entre 1 et 100, utiliser le générateur de nombres aléatoires pour mélanger la liste, puis extraire les 10 premières valeurs de la liste.

 int list[100], vektor[10]; for (i = 0; i < 100; i++) { list[i] = i; } for (i = 0; i < 100; i++) { int j = i + rand() % (100 - i); int temp = list[i]; list[i] = list[j]; list[j] = temp; } for (i = 0; i < 10; i++) { vektor[i] = list[i]; } 

Basé sur le commentaire de cobbal ci-dessous, il est même préférable de simplement dire:

 for (i = 0; i < 10; i++) { int j = i + rand() % (100 - i); int temp = list[i]; list[i] = list[j]; list[j] = temp; vektor[i] = list[i]; } 

Maintenant, c’est O (N) d’établir la liste mais O (M) de choisir les éléments aléatoires.

Générer simplement des nombres aléatoires et voir s’ils sont corrects est un mauvais moyen de résoudre ce problème en général. Cette approche prend toutes les valeurs possibles, les mélange puis prend le top dix. Ceci est directement analogue au fait de mélanger un jeu de cartes et de le dissortingbuer par le haut.

 #include  #include  #include  #define randrange(N) rand() / (RAND_MAX/(N) + 1) #define MAX 100 /* Values will be in the range (1 .. MAX) */ static int vektor[10]; int candidates[MAX]; int main (void) { int i; srand(time(NULL)); /* Seed the random number generator. */ for (i=0; i 

Pour plus d'informations, consultez la question 13.19 de la liste de FAQ comp.lang.c et la question 13.16 sur la génération de nombres aléatoires.

Je pense que cela va le faire (je n’ai pas essayé de le construire, donc les erreurs de syntaxe sont laissées à corriger comme exercice pour le lecteur). Il y a peut-être des manières plus élégantes, mais voici la solution de la force brute:

 int vektor[10];  int random; int uniqueflag; int i, j for(i = 0; i < 10; i++) { do { /* Assume things are unique... we'll reset this flag if not. */ uniqueflag = 1; random = rand() % 100+ 1; /* This loop checks for uniqueness */ for (j = 0; j < i && uniqueflag == 1; j++) { if (vektor[j] == random) { uniqueflag = 0; } } } while (uniqueflag != 1); vektor[i] = random; } 

Une solution consiste à vérifier si le tableau contient déjà le nouveau nombre aléatoire et, le cas échéant, créez-en un nouveau et réessayez.

Cela ouvre la possibilité (aléatoire) de ne jamais obtenir un nombre qui ne figure pas dans le tableau. Par conséquent, vous devez compter combien de fois vous vérifiez si le nombre est déjà dans le tableau et si le nombre dépasse MAX_DUPLICATE_COUNT, émettez une exception ou à peu près 🙂 (EDIT, vu que vous êtes en C. Oubliez l’exception par 🙂 code à la place: P)

Une solution rapide consiste à créer un tableau de masques de tous les nombres possibles initialisés à zéro et à définir une entrée si ce nombre est généré.

 int rand_array[100] = {0}; int vektor[10]; int i=0, rnd; while(i<10) { rnd = rand() % 100+ 1; if ( rand_array[rnd-1] == 0 ) { vektor[i++] = rnd; rand_array[rnd-1] = 1; } } 

Voici une méthode de temps moyen O (M).

Méthode: Si M <= N / 2, utilisez la procédure S (M, N) (ci-dessous) pour générer le tableau de résultats R et renvoie R. Si M> N / 2, utilisez la procédure S (NM, N) pour générer R, calculez ensuite X = {1..M}\R [le complément de R dans {1..M}], mélangez X avec shuffle de Fisher-Yates [dans le temps O (M)] et renvoyez X.

Dans le cas M> N / 2, où O (M) == O (N), il existe plusieurs méthodes rapides pour calculer le complément. Dans le code ci-dessous, par souci de brièveté, je n’ai inclus qu’un exemple de procédure S (M, N) codée en ligne dans main (). Le armsage Fisher-Yates est O (M) et est illustré dans la réponse principale à la question connexe n ° 196017 . Autres questions précédentes liées: # 158716 et # 54059 .

La raison pour laquelle S (M, N) prend O (M) au lieu de O (N) lorsque M coupons, l’attente E (t_k) est k H_k, à partir de laquelle E (t_ {k / 2}) = k (H_k – H_ {k / 2}) ou environ k * (ln (k) -ln (k / 2) + O (1)) = k * (ln (k / (k / 2)) + O (1)) = k * (ln (2) + O (1)) = O (k).

Procédure S (k, N): [Le corps de cette procédure est constitué d’une douzaine de lignes après le commentaire “Gen M nombres aléatoires distincts” dans le code ci-dessous.] Allouez et initialisez trois tableaux d’entiers M + 1 éléments H, L et V à toutes les valeurs -1. Pour i = 0 à M-1: insérez une valeur aléatoire v dans V [i] et dans le nœud sentinelle V [-1]. Obtenez l’une des M en-têtes de liste de H [v% M] et suivez cette liste jusqu’à trouver une correspondance avec v. Si la correspondance est V [-1], v est une nouvelle valeur; alors mettez à jour la tête de liste H [v% M] et le lien de liste L [i]. Si la correspondance n’est pas à V [-1], récupérez et testez un autre v, etc.

Le coût prévu pour chaque étape “suivre la liste” est O (1) car, à l’exception de la dernière, la longueur moyenne de la liste est inférieure à 1. (À la fin du traitement, les listes M contiennent M éléments, de sorte que la longueur moyenne augmente progressivement jusqu’à exactement 1.)

  // randomMofN - jiw 8 Nov 2011 // Re: https://stackoverflow.com/questions/1608181/ #include  #include  int main(int argc, char *argv[]) { int h, i, j, tM, M, N, par=0, *H, *L, *V, cxc=0; // Get M and N values ++par; M = 42; if (argc > par) M = atoi(argv[par]); ++par; N = 137; if (argc > par) N = atoi(argv[par]); tM = 3*M+3; H = malloc(tM*sizeof(int)); printf ("M = %d, N = %d %s\n", M, N, H?"":"\nmem error"); if (!H) exit(13); for (i=0; i=0); L[i] = H[h]; H[h] = i; } // Print results for (j=i=0; i66) j = printf ("\n"); } printf ("\ncxc %d\n", cxc); return 0; } 

J’aime l’algorithme de Floyd.

mais on peut prendre tout le nombre aléatoire de 0 à M (un ne pas à in ):

 #define M 10 #define N 100 unsigned char is_used[N] = { 0 }; /* flags */ int in, im; im = 0; for (in = N - M; in < N && im < M; ++in) { int r = rand() % (N + 1); /* generate a random number 'r' */ while (is_used[r]) { /* we already have 'r' */ r = rand() % (N + 1); } vektor[im++] = r + 1; /* +1 since your range begins from 1 */ is_used[r] = 1; } assert(im == M); 

Générez les premier et deuxième chiffres séparément. Mélangez-les plus tard si nécessaire. (syntaxe de la mémoire)

 int vektor[10]; int i = 0; while(i < 10) { int j = rand() % 10; if (vektor[j] == 0) { vektor[j] = rand() % 10 + j * 10; i ++;} } 

Cependant, les nombres seront presque séparés par n, 0

Sinon, vous devez conserver les numéros dans l'ordre ( O(n log n) ), afin que les personnes nouvellement générées puissent être rapidement vérifiées quant à leur présence ( O(log n) ).