Comment générer efficacement une liste de K nombres entiers non répétitifs compris entre 0 et une borne supérieure N [dupliquer]

https://stackoverflow.com/questions/158716

03-07-2019
|

Question

Cette question a déjà une réponse ici:

Nombres aléatoires uniques (non répétitifs) dans O (1)? 21 réponses

La question fournit toutes les données nécessaires: qu'est-ce qu'un algorithme efficace pour générer une séquence de K entiers non répétitifs dans un intervalle donné [0, N-1] . L'algorithme trivial (générer des nombres aléatoires et, avant de les ajouter à la séquence, les rechercher pour voir s'ils étaient déjà là) est très coûteux si K est grand et suffisamment proche pour N .

L'algorithme fourni dans la sélection efficace d'un un ensemble d’éléments aléatoires à partir d’une liste chaînée semble plus compliqué que nécessaire et nécessite une implémentation. Je viens de trouver un autre algorithme qui semble bien fonctionner, à condition de connaître tous les paramètres pertinents en une seule fois.

La solution

Le module aléatoire de la bibliothèque Python est extrêmement utile facile et efficace:

from random import sample
print sample(xrange(N), K)

La fonction

sample renvoie une liste de K éléments uniques choisis dans la séquence donnée.
xrange est un " émulateur de liste " ;, c’est-à-dire qu’il se comporte comme une liste de nombres consécutifs sans le créer en mémoire, ce qui le rend très rapide pour des tâches comme celle-ci.

Autres conseils

Dans L'art de la programmation informatique, Volume 2: Algorithmes séminumériques, troisième édition , Knuth décrit l'algorithme d'échantillonnage de sélection suivant:

Algorithme S (technique d’échantillonnage de sélection). Pour sélectionner n enregistrements au hasard dans un ensemble de N, où 0 & Lt; n & # 8804; N.

S1. [Initialize.] Réglez t & # 8592; 0, m & # 8592; 0. (Au cours de cet algorithme, m représente le nombre d’enregistrements sélectionnés jusqu’à présent, et t le nombre total d’enregistrements en entrée traités.)

S2. [Générer U.] Génère un nombre aléatoire U, uniformément réparti entre zéro et un.

S3. [Test.] Si (N & # 8211; t) U & # 8805; n & # 8211; m, passez à l'étape S5.

S4. [Select.] Sélectionnez l'enregistrement suivant pour l'échantillon et augmentez m et t de 1. Si m & Lt; n, allez à l'étape S2; sinon, l'échantillon est complet et l'algorithme se termine.

S5. [Ignorer.] Ignorez l'enregistrement suivant (ne l'incluez pas dans l'échantillon), augmentez t de 1 et revenez à l'étape S2.

Une implémentation peut être plus facile à suivre que la description. Voici une implémentation de Common Lisp qui sélectionne n membres aléatoires dans une liste:

(defun sample-list (n list &optional (length (length list)) result)
  (cond ((= length 0) result)
        ((< (* length (random 1.0)) n)
         (sample-list (1- n) (cdr list) (1- length)
                      (cons (car list) result)))
        (t (sample-list n (cdr list) (1- length) result))))

Et voici une implémentation qui n'utilise pas de récursivité et qui fonctionne avec toutes sortes de séquences:

(defun sample (n sequence)
  (let ((length (length sequence))
        (result (subseq sequence 0 n)))
    (loop
       with m = 0
       for i from 0 and u = (random 1.0)
       do (when (< (* (- length i) u) 
                   (- n m))
            (setf (elt result m) (elt sequence i))
            (incf m))
       until (= m n))
    result))

Il est en fait possible de le faire dans l’espace proportionnellement au nombre d’éléments sélectionnés plutôt qu’à la taille de l’ensemble que vous sélectionnez, quelle que soit la proportion de l’ensemble que vous sélectionnez. Vous faites cela en générant une permutation aléatoire, puis en sélectionnant comme ceci:

Choisissez un code de bloc, tel que TEA ou XTEA. Utilisez le repliement XOR pour réduire la taille du bloc au minimum de deux. plus grand que le jeu que vous choisissez. Utilisez la graine aléatoire comme clé du chiffre. Pour générer un élément n dans la permutation, chiffrez n avec le chiffre. Si le numéro de sortie ne figure pas dans votre jeu, chiffrez-le. Répétez jusqu'à ce que le nombre soit à l'intérieur du jeu. En moyenne, vous devrez faire moins de deux cryptages par nombre généré. Cela présente l'avantage supplémentaire que si votre graine est sécurisée sur le plan cryptographique, l'intégralité de votre permutation.

J'ai écrit à ce sujet beaucoup plus en détail ici .

Le code suivant (en C, origine inconnue) semble résoudre extrêmement bien le problème:

 /* generate N sorted, non-duplicate integers in [0, max[ */
 int *generate(int n, int max) {
    int i, m, a;    
    int *g = (int *)calloc(n, sizeof(int));
    if ( ! g) return 0;

    m = 0;
    for (i=0; i<max; i++) {
        a = random_in_between(0, max - i);
        if (a < n - m) {
            g[m] = i;
            m ++;
        }
    }
    return g;
 }

Est-ce que quelqu'un sait où je peux trouver plus de joyaux comme celui-ci?

Générer un tableau 0...N-1 rempli a[i] = i.

Mélangez ensuite les premiers K éléments.

Mélanger:

Démarrer J = N-1
Choisissez un nombre aléatoire 0...J (par exemple, R)
permuter a[R] avec a[J]
- puisque J peut être égal à 1, l'élément peut être échangé avec lui-même
soustrayez <=> à <=> et répétez.

Enfin, prenez les <=> derniers éléments.

Ceci sélectionne essentiellement un élément aléatoire de la liste, le déplace en dehors, puis sélectionne un élément aléatoire de la liste restante, etc. "

Fonctionne dans le temps O (K) et O (N) , nécessite un stockage O (N) .

La partie aléatoire est appelée Lecture aléatoire Fisher-Yates ou Le remaniement de Knuth , décrit dans le deuxième volume de L'Art de la programmation informatique.

Accélérez l’algorithme trivial en stockant les K nombres dans un magasin de hachage. Connaître K avant de commencer supprime toute l’inefficacité de l’insertion dans une carte de hachage, et vous bénéficiez toujours d’une recherche rapide.

Ma solution est orientée C ++, mais je suis certaine qu'elle pourrait être traduite dans d'autres langues, car elle est assez simple.

Tout d'abord, générez une liste chaînée avec K éléments allant de 0 à K
Ensuite, tant que la liste n'est pas vide, générez un nombre aléatoire compris entre 0 et la taille du vecteur
Prenez cet élément, poussez-le dans un autre vecteur et supprimez-le de la liste d'origine

Cette solution implique uniquement deux itérations de boucle, et aucune recherche de table de hachage ou quoi que ce soit du genre. Donc, dans le code actuel:

// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> random_list;

for(int i = 0; i < K; ++i) {
    sorted_list.push_back(i);
}

// Loop to K - 1 elements, as this will cause problems when trying to erase
// the first element
while(!sorted_list.size() > 1) {
    int rand_index = rand() % sorted_list.size();
    random_list.push_back(sorted_list.at(rand_index));
    sorted_list.erase(sorted_list.begin() + rand_index);
}                 

// Finally push back the last remaining element to the random list
// The if() statement here is just a sanity check, in case K == 0
if(!sorted_list.empty()) {
    random_list.push_back(sorted_list.at(0));
}

Étape 1: Générez votre liste d’entiers. Étape 2: effectuez la la mélodie du bonheur .

Notez que vous n’avez pas besoin de mélanger toute la liste, car l’algorithme Knuth Shuffle vous permet d’appliquer uniquement n shuffles, n étant le nombre d’éléments à renvoyer. La génération de la liste prendra toujours du temps proportionnellement à la taille de la liste, mais vous pouvez réutiliser votre liste existante pour tous les besoins de réorganisation futurs (en supposant que la taille reste la même) sans qu'il soit nécessaire de mélanger la liste partiellement réorganisée avant de redémarrer l'algorithme de réorganisation.

L’algorithme de base de Knuth Shuffle consiste à commencer par une liste d’entiers. Ensuite, vous échangez le premier entier avec un nombre quelconque dans la liste et renvoyez le premier (nouveau) entier actuel. Ensuite, vous échangez le deuxième entier avec un nombre quelconque dans la liste (sauf le premier) et renvoyez le deuxième (entier) actuel. Alors ... etc ...

C’est un algorithme absurdement simple, mais veillez à ne pas inclure l’élément actuel dans la liste lors de l’échange car vous risqueriez de casser l’algorithme.

La version d’échantillonnage de réservoir est assez simple:

my $N = 20;
my $k;
my @r;

while(<>) {
  if(++$k <= $N) {
    push @r, $_;
  } elsif(rand(1) <= ($N/$k)) {
    $r[rand(@r)] = $_;
  }
}

print @r;

C'est $ N lignes sélectionnées de manière aléatoire dans STDIN. Remplacez le & Lt; & Gt; / $ _ par quelque chose d'autre si vous n'utilisez pas les lignes d'un fichier, mais c'est un algorithme assez simple.

Si la liste est triée, par exemple, si vous souhaitez extraire K éléments de N, sans vous préoccuper de leur ordre relatif, un algorithme efficace est proposé dans l'article Un algorithme efficace pour l'échantillonnage aléatoire séquentiel <> / em> (Jeffrey Scott Vitter, Transactions ACM sur des logiciels mathématiques , vol. 13, n ° 1, mars 1987, pages 56 à 67.).

modifié pour ajouter le code dans c ++ à l'aide de boost. Je viens de le taper et il pourrait y avoir beaucoup d'erreurs. Les nombres aléatoires proviennent de la bibliothèque de boost, avec une graine stupide, alors ne faites rien de grave avec cela.

/* Sampling according to [Vitter87]. * * Bibliography * [Vitter 87] * Jeffrey Scott Vitter, * An Efficient Algorithm for Sequential Random Sampling * ACM Transactions on MAthematical Software, 13 (1), 58 (1987). */ #include <stdlib.h> #include <string.h> #include <math.h> #include <string> #include <iostream> #include <iomanip> #include <boost/random/linear_congruential.hpp> #include <boost/random/variate_generator.hpp> #include <boost/random/uniform_real.hpp> using namespace std; // This is a typedef for a random number generator. // Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand typedef boost::minstd_rand base_generator_type; // Define a random number generator and initialize it with a reproducible // seed. // (The seed is unsigned, otherwise the wrong overload may be selected // when using mt19937 as the base_generator_type.) base_generator_type generator(0xBB84u); //TODO : change the seed above ! // Defines the suitable uniform ditribution. boost::uniform_real<> uni_dist(0,1); boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni(generator, uni_dist); void SequentialSamplesMethodA(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method A. { int top=N-K, S, curr=0, currsample=-1; double Nreal=N, quot=1., V; while (K>=2) { V=uni(); S=0; quot=top/Nreal; while (quot > V) { S++; top--; Nreal--; quot *= top/Nreal; } currsample+=1+S; cout << curr << " : " << currsample << "\n"; Nreal--; K--;curr++; } // special case K=1 to avoid overflow S=floor(round(Nreal)*uni()); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } void SequentialSamplesMethodD(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method D. { const int negalphainv=-13; //between -20 and -7 according to [Vitter87] //optimized for an implementation in 1987 !!! int curr=0, currsample=0; int threshold=-negalphainv*K; double Kreal=K, Kinv=1./Kreal, Nreal=N; double Vprime=exp(log(uni())*Kinv); int qu1=N+1-K; double qu1real=qu1; double Kmin1inv, X, U, negSreal, y1, y2, top, bottom; int S, limit; while ((K>1)&&(threshold<N)) { Kmin1inv=1./(Kreal-1.); while(1) {//Step D2: generate X and U while(1) { X=Nreal*(1-Vprime); S=floor(X); if (S<qu1) {break;} Vprime=exp(log(uni())*Kinv); } U=uni(); negSreal=-S; //step D3: Accept ? y1=exp(log(U*Nreal/qu1real)*Kmin1inv); Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real)); if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true //step D4 Accept ? y2=0; top=Nreal-1.; if (K-1 > S) {bottom=Nreal-Kreal; limit=N-S;} else {bottom=Nreal+negSreal-1.; limit=qu1;} for(int t=N-1;t>=limit;t--) {y2*=top/bottom;top--; bottom--;} if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv)) {//Accept ! Vprime=exp(log(uni())*Kmin1inv); break; } Vprime=exp(log(uni())*Kmin1inv); } // Step D5: Select the (S+1)th record currsample+=1+S; cout << curr << " : " << currsample << "\n"; curr++; N-=S+1; Nreal+=negSreal-1.; K-=1; Kreal-=1; Kinv=Kmin1inv; qu1-=S; qu1real+=negSreal; threshold+=negalphainv; } if (K>1) {SequentialSamplesMethodA(K, N);} else { S=floor(N*Vprime); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } } int main(void) { int Ntest=10000000, Ktest=Ntest/100; SequentialSamplesMethodD(Ktest,Ntest); return 0; } $ time ./sampling|tail

donne la sortie suivante sur mon ordinateur portable

99990 : 9998882 99991 : 9998885 99992 : 9999021 99993 : 9999058 99994 : 9999339 99995 : 9999359 99996 : 9999411 99997 : 9999427 99998 : 9999584 99999 : 9999745 real 0m0.075s user 0m0.060s sys 0m0.000s

Ce code Ruby présente la méthode Échantillonnage de réservoir, algorithme R . A chaque cycle, je sélectionne n=5 entiers aléatoires uniques dans [0,N=10) intervalle:

t=0 m=0 N=10 n=5 s=0 distrib=Array.new(N,0) for i in 1..500000 do t=0 m=0 s=0 while m<n do u=rand() if (N-t)*u>=n-m then t=t+1 else distrib[s]+=1 m=m+1 t=t+1 end #if s=s+1 end #while if (i % 100000)==0 then puts i.to_s + ". cycle..." end end #for puts "--------------" puts distrib

sortie:

100000. cycle... 200000. cycle... 300000. cycle... 400000. cycle... 500000. cycle... -------------- 250272 249924 249628 249894 250193 250202 249647 249606 250600 250034

tous les entiers compris entre 0 et 9 ont été choisis avec une probabilité presque identique.

Il s’agit essentiellement de algorithme de Knuth appliqué à des séquences arbitraires (cette réponse possède en fait une version LISP de celle-ci). L'algorithme est O (N) dans le temps et peut être O (1) en mémoire si la séquence y est transmise comme indiqué dans @MichaelCramer answer .

Voici un moyen de le faire en O (N) sans espace de stockage supplémentaire. Je suis presque sûr que ce n'est pas une distribution purement aléatoire, mais c'est probablement assez proche pour de nombreuses utilisations.

/* generate N sorted, non-duplicate integers in [0, max[ in O(N))*/ int *generate(int n, int max) { float step,a,v=0; int i; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; for (i=0; i<n; i++) { step = (max-v)/(float)(n-i); v+ = floating_pt_random_in_between(0.0, step*2.0); if ((int)v == g[i-1]){ v=(int)v+1; //avoid collisions } g[i]=v; } while (g[i]>max) { g[i]=max; //fix up overflow max=g[i--]-1; } return g; }

C'est le code Perl. Grep est un filtre et, comme toujours, je n'ai pas testé ce code.

@list = grep ($_ % I) == 0, (0..N);

I = intervalle

N = Limite supérieure

Obtenez uniquement des nombres correspondant à votre intervalle via l'opérateur de module.

@list = grep ($_ % 3) == 0, (0..30);

renverra 0, 3, 6, ... 30

C'est du pseudo code Perl. Vous devrez peut-être le modifier pour le compiler.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow