Chọn phần tử mảng ngẫu nhiên thỏa mãn thuộc tính nhất định

Question

Giả sử tôi có một danh sách, được gọi là elements, mỗi phần tử có hoặc không thỏa mãn một số thuộc tính boolean p. Tôi muốn chọn một trong các yếu tố thỏa mãn p một cách ngẫu nhiên với phân bố đồng đều. Tôi không biết trước bao nhiêu mặt hàng thỏa mãn tài sản này p.

đoạn mã sau sẽ làm được điều này ?:

pickRandElement(elements, p) 
    randElement = null 
    count = 0 
    foreach element in elements 
      if (p(element)) 
       count = count + 1 
       if (randInt(count) == 0) 
        randElement = element 

    return randElement 

(randInt(n) lợi nhuận một ngẫu nhiên int k với 0 <= k < n.)

Answer 1

Nó hoạt động bằng toán học. Có thể được chứng minh bằng cảm ứng.

Làm việc rõ ràng cho yếu tố n = 1 thỏa mãn p.

Đối với các yếu tố n + 1, chúng tôi sẽ chọn phần tử n + 1 với xác suất 1/(n + 1), vì vậy xác suất của nó là OK.Nhưng làm thế nào mà có hiệu lực xác suất cuối cùng của việc lựa chọn một trong những yếu tố n trước?

Mỗi n trước đó có cơ hội được chọn với xác suất 1/n, cho đến khi chúng tôi tìm thấy phần tử n + 1. Bây giờ, sau khi tìm n + 1, có 1/(n + 1) cơ hội mà phần tử n + 1 được chọn, do đó, có một n/(n + 1) cơ hội mà phần tử đã chọn trước đó vẫn được chọn. Có nghĩa là xác suất cuối cùng của nó là được chọn sau khi tìm thấy n + 1 là 1/n * (n/n + 1) = 1/n + 1 - đó là xác suất chúng ta muốn cho tất cả các phần tử n + 1 để phân bố đều.

Nếu nó hoạt động cho n = 1, và nó hoạt động cho n + 1 cho n, sau đó nó hoạt động cho tất cả n.

Answer 2

Vâng, tôi tin như vậy.

Lần đầu tiên bạn gặp phải một yếu tố phù hợp, bạn chắc chắn chọn nó. Lần sau, bạn chọn giá trị mới với xác suất là 1/2, do đó, mỗi một trong hai phần tử đều có cơ hội như nhau. Lần sau, bạn chọn giá trị mới với xác suất 1/3, để mỗi phần tử khác có xác suất bằng 1/2 * 2/3 = 1/3.

Tôi đang cố gắng để tìm một bài viết trên Wikipedia về chiến lược này, nhưng thất bại cho đến nay ...

Lưu ý rằng tổng quát hơn, bạn chỉ cần chọn một mẫu ngẫu nhiên ra khỏi một chuỗi có độ dài chưa biết. Trình tự của bạn xảy ra được tạo ra bằng cách lấy một chuỗi ban đầu và lọc nó, nhưng thuật toán không yêu cầu phần đó chút nào.

tôi nghĩ rằng tôi đã có một nhà điều hành LINQ trong MoreLINQ để làm điều này, nhưng tôi không thể tìm thấy nó trong kho ... EDIT: May mắn thay, nó vẫn còn tồn tại từ this answer:

public static T RandomElement<T>(this IEnumerable<T> source, 
           Random rng) 
{ 
    T current = default(T); 
    int count = 0; 
    foreach (T element in source) 
    { 
     count++; 
     if (rng.Next(count) == 0) 
     { 
      current = element; 
     }    
    } 
    if (count == 0) 
    { 
     throw new InvalidOperationException("Sequence was empty"); 
    } 
    return current; 
} 

Answer 3

Đối vì lợi ích rõ ràng, tôi sẽ cố gắng:

pickRandElement(elements, p) 
    OrderedCollection coll = new OrderedCollection 
    foreach element in elements 
      if (p(element)) 
       coll.add(element) 
    if (coll.size == 0) return null 
    else return coll.get(randInt(coll.size)) 

Đối với tôi, mà làm cho nó rõ ràng hơn NHIÊU những gì bạn đang cố gắng làm và là tự tài liệu. Ngày đầu đó, nó đơn giản và thanh lịch hơn, và bây giờ rõ ràng rằng mỗi người sẽ được chọn với một bản phân phối đồng đều.

Answer 4

Trong Thực hành lập trình, trg. 70, (The Markov Chain Algorithm) có một thuật toán tương tự cho rằng:.

[...] 
    nmatch = 0; 
    for (/* iterate list */) 
    if (rand() % ++nmatch == 0) /* prob = 1/nmatch */ 
     w = suf->word; 
[...] 

"Chú ý các thuật toán để lựa chọn một mục một cách ngẫu nhiên khi chúng ta không biết làm thế nào nhiều mặt hàng có Các biến nkhớp đếm số lượng các trận đấu như danh sách được scan. Khái niệm

rand() % ++nmatch == 0 

increments nkhớp và sau đó đúng với xác suất 1/nkhớp."

Answer 5

decowboy có một bằng chứng tốt đẹp mà này hoạt động trên TopCoder