Générer k nombres distincts inférieurs à n

Question

La tâche est la suivante: générer k nombres positifs distincts inférieurs à n sans duplication.

Ma méthode est la suivante.

d'abord créer la taille du tableau de k où écrire ces chiffres:

int a[] = new int[k]; 

//Now I am going to create another array where I check if (at given number 
//position is 1 then generate number again, else put this number in an 
//array and continue cycle. 

je mets un morceau ici de code et des explications.

int a[]=new int[k]; 
int t[]=new int[n+1]; 
Random r=new Random(); 
for (int i==0;i<t.length;i++){ 
    t[i]=0;//initialize it to zero 
} 

int m=0;//initialize it also 
for (int i=0;i<a.length;i++){ 
    m=r.nextInt(n);//random element between 0 and n 
    if (t[m]==1){ 
     //I have problems with this. I want in case of duplication element 
     //occurs repeat this steps afain until there will be different number. 
    else{ 
     t[m]=1; 
     x[i]=m; 
    } 
} 

Donc je remplis concret mon problème: si t [m] == 1. Cela signifie que cet élément se produit déjà, donc je veux générer un nouveau nombre, mais le problème est que le nombre de nombres générés sera ne pas être k parce que si i == 0 et se produit élément dupliqué et nous écrivons continuer alors il passera à i == 1. J'ai besoin de goto pour l'étape de répétition. Ou:

for (int i=0;i<x.length;i++){ 
    loop: 
     m=r.nextInt(n); 

    if (x[m]==1){ 
     continue loop; 
    } 
    else{ 
     x[m]=1; 
     a[i]=m; 
     continue; //Continue next step at i=1 and so on. 
    } 
} 

J'ai besoin de ce code en Java.

Answer 1

Il semble que vous ayez besoin d'un algorithme d'échantillonnage aléatoire. Vous voulez être en mesure de choisir m éléments aléatoires de l'ensemble {0,1,2,3 ..., n-1}. Voir this post, où j'ai écrit environ 5 algorithmes efficaces pour l'échantillonnage aléatoire.

Suite est la mise en œuvre de Floyd, qui peut être utile dans votre cas:

private static Random rnd = new Random(); 
... 
public static Set<Integer> randomSample(int n, int m){ 
    HashSet<Integer> res = new HashSet<Integer>(m); 
    for(int i = n - m; i < n; i++){ 
     int item = rnd.nextInt(i + 1); 
     if (res.contains(item)) 
      res.add(i); 
     else 
      res.add(item); 
    } 
    return res; 
} 

Answer 2

Create an array arr with n elements (1..n); 
for i=1 to k { 
    result[i] = arr[rand] 
    delete arr[result[1]] 
}