Генерировать k различных чисел меньше чем n

Question

Задача состоит в следующем: генерировать k различных положительных чисел, меньших, чем n, без дублирования.

Мой метод следующий.

Сначала создайте размер массива k, где мы должны написать эти числа:

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.

Я положил здесь часть кода и объяснений.

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;
    }
}

Итак, я заполняю конкретную мою проблему: если t [m] == 1. Это значит, что этот элемент встречается уже, поэтому я хочу сгенерировать новое число, но проблема в том, что число сгенерированных номеров будет не быть k, потому что если i == 0 и встречается повторяющийся элемент, и мы пишем продолжить, то он переключится на i == 1. Мне нужно как goto для повторного шага. Или:

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.
    }
}

Мне нужен этот код на Java.

Answer 1

Кажется, вам нужен алгоритм случайной выборки. Вы хотите иметь возможность выбрать m случайных элементов из набора {0,1,2,3 ..., n-1}.

См. этот пост , где я написал о 5 эффективных алгоритмах для случайной выборки.

Ниже приведена реализация Флойда, которая может быть полезна в вашем случае:

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]]
}