총 항목 수를 모른 채 임의의 항목 선택

Question

임의의 항목을 선택해야하는 경우가 있습니다. 그러나 총 항목 수를 알지 못하고 엄청난 배열을 만들고 싶지 않습니다. 그런 다음 항목을 선택하십시오. 당신이, 내가 정말 필요가 없습니다 거대한 수집을 짓고 있어요 볼 수 있듯이

List<string> items; 
while (true) 
{ 
    string item = GetNextItem(); 
    if (item == null) 
     break; 
} 
int index = random.GetNext(0, items.count); 

, 나는 그냥 0 사이의 임의의 숫자와 숫자의 필요 : 예를 들어, 내가 지금 무엇을 가지고 항목. 여기에 내가 일을 생각하고 무엇이며, 그것은 작동하지만, 내가 거기에 전문가의 그것과 오류 찾을 수 있는지 알고 싶습니다 :

int index = -1; 
int total; 
string selectedItem; 
while (true) 
{ 
    string item = GetNextItem(); 
    if (item == null) 
     break; 

    ++total; 
    int rnd = random.Next(0, total); 
    if (rnd == total- 1) 
    { 
     index = total- 1; 
     selectedItem = item; 
    } 
} 

이 나에게 내 인덱스 번호를 제공을하고, 무작위로 선택한 항목. 이것에 대한 나의 생각은 예를 들어 총 3 개의 항목이있을 때 0에서 2 사이의 난수를 선택하고 2와 같으면 무시하지 않을 경우 새 항목을 선택한 항목으로 사용한다는 것입니다. 총 아이템 수가 증가함에 따라, 새로운 아이템이 선택 될 확률은 그에 따라 감소합니다.

이 방법이 "좋음"입니까? 배열을 만들고 나중에 항목을 선택할 때 "임의"로 사용합니까? 가능한 한 빨리? 무작위 수에 대한 나의 무지를 통해 나를 인도 해주세요. :)

Answer 1

당신이하고있는 일이 효과가 있습니다. 이 경우 현재 선택을

될 것 100 %의 기회가,

1. 은 첫 번째 항목을 선택합니다 : 여기

   약간 더 명확한 알고리즘을 만들 수도 그것의 재 작성의 두 번째 항목 인 은 1/2 기회가됩니다. 은 현재 선택 사항을 대체합니다 (계산을 수행하면 첫 번째 항목이 50 % 확률이고 두 번째 항목은 50 % 확률 임).)

2. 제 항목 (다시, 수학 각 항목이 1/3 인 대한 확률)가 현재 선택을 대체하는 1/3 기회 네 번째 항목이있는 경우
3. 가 존재하고, 존재 당신이 rand.Next(0,x) == 0 말하여 1/x 기회를 계산할 수 있어야한다 1/4 기회 는 등 ... 현재 선택
4. 를 대체 할 ...

주 (또는 0을 사이에 다른 정수 및 x - 1; 당신은 total - 1을 사용하는 것을 귀찮게하지 않아도됩니다.

실제로는 매우 깔끔한 접근 방식입니다. 처음에는 당신이 묻고있는 일을하는 좋은 방법이 없을 것이라고 생각했습니다!

Answer 2

첫 번째 코드 스 니펫에서는 items.count를 사용하므로 가지고있는 요소의 수를 알 수 있습니다. 이 필요하므로 각 요소는 동일한 기회가 선택됩니다.

작성한대로 0 < = i < items.count와 같은 난수 i를 생성하면 목록의 요소 i에 빠르게 액세스하려고 시도합니다. (연결된 목록은 데이터 구조의 좋은 선택이 아닐 수도 있습니다.)

예상되는 N 개의 항목 수를 알고있는 경우 items.count 대신이 값을 사용할 수 있습니다.

두 번째 코드 스 니펫에서 "total"을 0으로 초기화해야 할 수도 있습니다.

Answer 3

당신의 접근 방식은 좋아 보인다. 당신이 하나를 선택

1 항목을 =

이

2 개 항목 = 50 %의 확률로 당신이 3 항목을 선택 1

3 개 항목 = 33 %의 확률로 대체 할 2 항목을 선택 선택됩니다 67 %의 확률로 처음 두 항목

의 당신이 4 항목을 선택

4 개 항목 = 25 %의 확률로, 당신은 선택 75 %의 확률로 ...

...

의 대부분에 따라서는 반대로 오 여기에 대한 응답은 균등 확률 분포를 제공하는 효과적인 솔루션이라고 생각합니다. 그것은 문제가되지 않기 때문에

int rnd = random.Next(0, total); 
    if (rnd == 0) 

1/N 확률을 얻을 수 있도록 테스트 총-1 값의 어느 :

당신은 무작위 검사를 단순화 할 수있다.

Answer 4

유도로 증명할 수 있습니다.
1의 경우는 참입니다.
n에 대해 true 인 경우; n + 1의 경우는 true입니다.
=> prob. 첫 번째 n 요소 선택 = 1/n
=> sice prob. (n + 1) 번째 요소를 선택하는 문제는 1/(n + 1)
=> n 번째 요소를 선택하지 않은 경우의 확률은 n/(n + 1)
=> 첫 번째 n 1/n * (n/n + 1) = 1/n + 1을 더한 후 요소들