Lấy một phần tử ngẫu nhiên trong danh sách liên kết một hướng bằng một lần đi ngang

Question

Tôi có một danh sách liên kết hướng đơn mà không biết kích thước của nó.

Tôi muốn lấy một phần tử ngẫu nhiên trong danh sách này và tôi chỉ có một lần cơ hội để duyệt qua danh sách. (Tôi không được phép đi qua hai lần trở lên)

Thuật toán cho vấn đề này là gì? Cảm ơn!

Answer 1

này chỉ reservoir sampling với một hồ chứa kích thước là 1.

Về cơ bản nó là thực sự đơn giản

1. Chọn phần tử đầu tiên không phân biệt (đối với một danh sách dài 1, yếu tố đầu tiên luôn luôn là mẫu).
2. Đối với mọi phần tử khác với xác suất 1/n trong đó n là số nguyên tố được quan sát cho đến nay, bạn thay thế phần tử đã chọn bằng phần tử hiện tại bạn đang sử dụng.

Điều này được lấy mẫu thống nhất, vì xác suất chọn bất kỳ phần tử nào vào cuối ngày là 1/n (tập thể dục cho người đọc).

Answer 2

Đây có thể là câu hỏi phỏng vấn. Lấy mẫu lấy mẫu được sử dụng bởi nhà khoa học dữ liệu để lưu trữ dữ liệu có liên quan trong bộ nhớ hạn chế từ luồng dữ liệu lớn.

Nếu bạn có để thu thập các yếu tố k từ bất kỳ mảng với n phần tử, như vậy mà bạn khả năng của mỗi yếu tố thu thập nên cùng (k/n), bạn thực hiện theo hai bước,

1) Lưu trữ các yếu tố k đầu tiên trong bộ nhớ. 2) Khi phần tử tiếp theo (k + 1) xuất phát từ luồng rõ ràng là bạn không còn chỗ trống trong bộ sưu tập của mình nữa. Tạo một số ngẫu nhiên từ o đến n, nếu số ngẫu nhiên được tạo nhỏ hơn k giả sử l, thay thế dung lượng lưu trữ [ l] với phần tử (k + 1) từ luồng.

Bây giờ, quay trở lại câu hỏi của bạn, kích thước lưu trữ ở đây là 1.So bạn sẽ chọn nút đầu tiên, lặp qua danh sách cho phần tử thứ hai.Bây giờ tạo số ngẫu nhiên, nếu 1 phần tử lưu trữ từ danh sách

Answer 3

Câu hỏi này có thể được thực hiện bằng cách sử dụng lấy mẫu hồ chứa. Nó dựa trên việc chọn k item ngẫu nhiên trong số n item, nhưng ở đây n có thể rất lớn (không cần phải phù hợp với bộ nhớ!) Và (như trong trường hợp của bạn) không biết ban đầu.

Các wikipedia có một thuật toán có thể hiểu được mà tôi trích dẫn dưới đây:

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done 

Câu hỏi đặt ra đòi hỏi chỉ có 1 giá trị để chúng ta lấy k = 1.

C thực hiện:

https://ideone.com/txnsas