Génération de m nombres aléatoires distincts dans la plage [0..n-1].

Question

J'ai deux méthodes pour générer m nombres aléatoires distincts dans l'intervalle [0..n-1].

Méthode 1 :

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

Méthode 2 :

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

La première méthode est plus efficace lorsque n est beaucoup plus grand que m, tandis que la seconde est plus efficace dans le cas contraire. Mais "beaucoup plus grand" n'est pas une notion si stricte, n'est-ce pas ? :)

Pregunta: Quelle formule de n et m dois-je utiliser pour déterminer si la méthode1 ou la méthode2 sera plus efficace ? (en termes d'espérance mathématique du temps d'exécution)

Answer 1

Je ne conseille pas cette méthode mais elle fonctionne.

#include <iostream>
#include <random>
#include <ctime>

using namespace std;

int randArray[26];
int index = 0;

bool unique(int rand) {

    for (int i = 0; i < index; i++)
        if (rand == randArray[i])
            return false;
    index++;
    return true;
}

int main()
{
    srand(time(NULL));

    for (int i = 1; i < 26; i++)
        randArray[i] = -1;

    for (int i = 0; i < 26; i++) {

        randArray[i] = rand() % 26;

        while (!unique(randArray[i])) {
            randArray[i] = rand() % 26;
        }
    }

    for (int i = 0; i < 26; i++) {
        cout << randArray[i] << " ";
    }

    cout << "\n" << index << endl;

    return 0;
}