n보다 작은 k 개의 고유 번호 생성

Question

작업은 다음과 같습니다. 복제없이 n보다 작은 k 개의 양수를 생성하십시오.

내 방법은 다음과 같습니다.

먼저 우리가이 번호를 작성해야 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. 그것은이 요소가 이미 발생 했으므로 새 번호를 생성하기 위해 을 생성하지만 문제는 생성 된 숫자의 수입니다. 은 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

임의의 샘플링 알고리즘이 필요합니다. 집합 {0,1,2,3 ..., n-1}에서 m 개의 임의 항목을 선택할 수 있기를 원합니다.

this post을 참조하십시오. 무작위 샘플링을위한 약 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]] 
}