Generate k distinct numbers less than n
The task is as follows: generate k distinct positive numbers less than n without duplication.
My method is as follows.
First create the size of the array k, where we should write these numbers:
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.
I put the code and explanations here.
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;
}
}
So I fill my problem: if t [m] == 1. This means that this element is happening already, so I want to generate a new number, but the problem is that the number of generated numbers will not be k, because if I == 0 and a duplicate element occurs, and we write continue, then it will switch to i == 1. I need to go to a repeated step. Or:
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.
}
}
I need this code in Java.
a source to share
It seems you want a random sampling algorithm. You want to select m random elements from the set {0,1,2,3 ..., n-1}.
See this post where I wrote about 5 efficient algorithms for random sampling.
Below is Floyd's implementation that might be helpful in your case:
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;
}
a source to share