stl 컨테이너에서 임의의 요소 n 개를 그립니다.

Question

대체로 this question과 같지만 선택할 컨테이너는 가능한 한 일반적입니다 (즉, Forward Container 또는 심지어 간단하게 Container). 미립자 컨테이너에 .size()가 있고 그것을 두 번 (크기를 계산하고 결과 집합을 얻기 위해 한 번) 보았을 것이라고 가정해서는 안됩니다.

저는 3-5 라인 범위에서 무언가를 기대하고 있기 때문에 조금 더 복잡하고 몇 가지 의존성이있는 해결책이 하나 있습니다.

Answer 1

'무작위 요소'는 균등하게 분포 된 요소를 의미한다고 가정합니다.

시퀀스의 길이에 대해 알지 못해서 미리 계산할 수 없으므로 임의 순서를 점진적으로 만들어야합니다. 그러기 위해 우리가 사용하는 확률이 모두 합쳐져서 우리가 원했던 결과를 얻었 으면합니다.

두 단계로 실행합니다. 먼저 순서 번호 중 어느 것이 그려지는지 결정한 다음 필요에 따라 임의의 순서를 선택할 수 있습니다 (질문에서 명확하지 않음). 그리고 나에게 더 쉽기 때문에 너의 N 'K'라고 부를 것이다.

먼저 K 개의 그려진 요소를 보유하기 위해 K 요소 배열을 만듭니다. 시퀀스의 첫 번째 K 요소로 이동하여 배열에 복사합니다. 시퀀스에 K 요소가없는 경우 "No can do"라고 말합니다.

이제 K 크기 시퀀스의 K 개의 임의 요소가 있음을 알았습니다. 시퀀스가 끝나면 완료됩니다. 그렇지 않은 경우 K + 1 크기의 시퀀스가 ​​있음을 알 수 있습니다. 여기에는 K + 1 번째 항목이 선택되거나 그렇지 않은 두 가지 옵션이 있습니다.

K + 1 번째 항목을 선택할 확률은 무엇입니까? K + 1의 항목이 이 아니고이 아닌 확률을 계산하는 것이 더 쉽습니다. K + 1 요소가 나타나지 않는 경우 K 요소를 선택하는 K + 1 및 K (K 이상 K) 방법 만 선택할 수있는 (K + K 초과) 방법이 있습니다. 그래서 (K over K)/(K + 1 over K)는 K + 1 번째 항목이 선택되지 않을 확률입니다.

따라서 0과 1 사이의 임의의 숫자를 선택하십시오. 1/(K + 1)보다 작 으면 K + 1 번째 요소가 시퀀스에 나타나지 않습니다. 난수가 그 이상인 경우 K + 1 번째 요소가 시퀀스에 나타납니다. 1과 K 사이의 무작위 요소를 선택하고 K + 1 번째 요소로 바꿉니다.

이제 K + 2 번째 항목 인 다음 항목으로 이동합니다. 그리고 우리는 다시 같은 일을합니다. 시퀀스에 K + 2 번째 항목이 나타나지 않을 확률은 (K + 1 over K)/(K + 2 over K)입니다.

시퀀스를 모두 사용할 때까지 수행하십시오. 그런 다음 시퀀스에서 무작위로 선택된 K 개의 요소 목록이 있습니다.

랜덤하게 (적어도 짧은 시퀀스에는 해당되지 않음) 순서가 지정되지 않으므로 임의의 K 크기 순열을 선택할 수 있습니다.

면책 조항 : 확률은 암캐이며, 나에게 맞는 것처럼 보이지만, 내가 놓친 기회가있어 최종 결과가 균등하게 분배되지 않습니다. 다른 사람들은 꽤 빨리 말할 것입니다.