Set S các số n - có một tập hợp con với khả năng của mỗi phần tử của S occuring trong nó bằng

Question

Tôi có vấn đề này

Bạn đang đưa ra một tập S các số n. Bạn phải chọn một tập hợp con S ′ của số k từ S sao cho xác suất của mỗi phần tử S xảy ra trong S ′ bằng nhau (tức là, mỗi số được chọn với xác suất k/n). Bạn chỉ có thể thực hiện một lần vượt qua các con số. Điều gì sẽ xảy ra nếu n không xác định?

và tôi thậm chí có một giải pháp: http://www.algorithm.cs.sunysb.edu/algowiki/index.php/TADM2E_2.43

Tuy nhiên: Tôi không hiểu nội dung vấn đề gì cả.

Tôi được cung cấp một S số n được đặt. Khỏe. Tôi cần chọn một tập hợp con (2^n tập con) của số k sao cho xác suất của mỗi phần tử S xảy ra trong S 'bằng nhau ... câu trả lời hiển nhiên đối với tôi là chỉ lấy tập S rỗng : mỗi phần tử trong S sẽ có xác suất 0 trong S '.

Nếu điều này không được chấp nhận (và nó phải được ghi rõ), tôi giả sử tôi nên đếm phần tử lặp lại nhiều nhất (xuất hiện T) trong S và làm cho mọi phần tử khác có chính xác T trường hợp trong S ' vẫn phải là tập con nếu các phần tử được chứa trong S).

Tôi không thực sự hiểu giải pháp xếp hàng ưu tiên, cũng như xác suất k/n. Ai đó có thể giúp tôi với điều này?

Answer 1

Đây là một vấn đề rất nổi tiếng với kỹ thuật kết quả được gọi là Reservoir Sampling - một thuật toán rất hữu ích để xử lý luồng dữ liệu lớn. Liên kết trước có thể cung cấp cho bạn cài đặt, động lực và giải thích chính xác về giải pháp.