Cho một mảng các phép toán, cách hiệu quả nhất để chọn chỉ mục của một giá trị TRUE ngẫu nhiên là gì?

Question

Bạn được cung cấp một mảng có kích thước n, chứa các giá trị boolean tùy ý.

Cách nhanh nhất để trả lại chỉ mục của giá trị TRUE ngẫu nhiên là gì.

Thuật toán sẽ trả về ngẫu nhiên bất kỳ chỉ mục nào có chứa TRUE.

Answer 1

Something như thế này:

int count = 0; 
int index = -1; 
for (int i = 0; i != n; ++i) 
{ 
    if (values[i]) 
    { 
     ++count; 
     if (unit_random <= 1.0f/count) 
     { 
      index = i; 
     } 
    } 
} 

Vì vậy, trong 4 giá trị ví dụ như bạn nhận được các xác suất sau cho chỉ số của họ:

1: (1/1) * (1/2) * (2/3) * (3/4) = 1/4 
2: (1/2) * (2/3) * (3/4) = 1/4 
3: (1/3) * (3/4) = 1/4 
4: 1/4 = 1/4 

EDIT: Như Steve Jessop chỉ ra những điểm so sánh nổi cuối cùng sẽ dẫn đến một lựa chọn rất không đồng đều. Giả sử unit_random được định nghĩa là rand()/RAND_MAX sự so sánh có thể được thay đổi để:

typedef unsigned long long u64; 
u64 product = u64(count) * rand(); 
if (product <= u64(RAND_MAX)) 

này sẽ không cung cấp phân phối hoàn hảo do tính chất rời rạc của rand nhưng nó sẽ được tốt hơn.

Answer 2

Nó không hoàn toàn rõ ràng những gì "ngẫu nhiên distibuted" có nghĩa là. Nó có nghĩa là "với một số phân phối không rõ"? Nếu vậy, giả sử tất cả các phân phối có thể đều có thể xảy ra, do đó, "phân phối dự kiến" (giống như "giá trị dự kiến") là thống nhất ("trung bình" của tất cả các bản phân phối có thể.) Sau đó, bất kỳ chỉ mục nào là TRUE với xác suất 1/2. Vì vậy, nhiệm vụ của bạn trở thành nhiệm vụ lặp qua mảng càng nhanh càng tốt. Bắt đầu từ đầu, như bạn thường sẽ lặp lại một mảng, cho đến khi bạn gặp phải một giá trị TRUE.

Answer 3

Để trả lại, trước hết bạn phải tính giá trị True (không có cách nào để bỏ qua) và tích lũy chỉ mục của chúng trong một mảng khác. Và sau khi đếm, bạn cần tạo ra số nguyên ngẫu nhiên từ 0 đến N-1 (trong đó N là số giá trị True) và chọn giá trị từ mảng đã tạo.

trong pseudo-python:

indices=[] 

for i,val in enumerate(arr): 
    if val: 
     indices.append(i) 
randi = randint(0,len(indices)-1) 
return indices[randi] 

Answer 4

Giải pháp nhanh nhất - giả sử bạn không chọn lặp đi lặp lại trên cùng một mảng - là để chọn một chỉ số ngẫu nhiên, trả lại nếu đó là sự thật, và lặp lại nếu không muốn nói. Trong trường hợp tốt nhất, nơi tất cả các mục là đúng, đây là O (1); trong trường hợp xấu nhất, chỉ có một mục là đúng, đây là O (n) (mỗi lần thử có 1/n cơ hội đánh giá trị thực duy nhất, có nghĩa là số lần thử n mong đợi). Điều này không tệ hơn bất kỳ giải pháp được đăng nào khác.

Nếu bạn mong đợi mảng thường gần như là tất cả sai, mặc dù, bạn có thể muốn chọn giải pháp khác, vì phương sai trong thời gian chạy của phương thức ngẫu nhiên này sẽ cao.

Answer 5

Giải pháp đơn giản: Tạo một hoán vị của các chỉ số có thể (1: n) và theo thứ tự của chỉ số hoán vị trở lại nếu giá trị tương ứng là đúng

def randomTrue(x): 
    perm = randomPermute(0:len(x)) 
    for i in perm: 
     if x[i]: 
      return i