Tạo số là phạm vi (1, n) nhưng không có trong danh sách (i, j)

Question

Làm cách nào để tạo số ngẫu nhiên nằm trong phạm vi (1,n) nhưng không nằm trong một danh sách nhất định (i,j)?

Ví dụ: phạm vi là (1,500), danh sách là [1,3,4,45,199,212,344].

Lưu ý: Danh sách này có thể không được sắp xếp

Answer 1

Rejection Sampling

Một phương pháp là lấy mẫu từ chối:

1. Tạo một số x trong khoảng (1, 500)
2. là x trong danh sách các giá trị không được phép của bạn? (Có thể sử dụng một hash-thiết cho việc kiểm tra này.)
   • Nếu có, trở lại bước 1
   • Nếu không, x là giá trị ngẫu nhiên của bạn, thực hiện

này sẽ hoạt động tốt nếu tập hợp các giá trị được phép của bạn lớn hơn đáng kể so với tập hợp các giá trị không được phép:
nếu có G giá trị tốt có thể và B giá trị có thể xấu, thì số lần dự kiến ​​bạn sẽ phải lấy mẫu x từ G + B giá trị cho đến khi bạn nhận được một giá trị tốt là (G + B)/G (kỳ vọng của phân phối hình học liên quan). (Bạn có thể cảm nhận được kiểm tra điều này. Như G đi đến vô cùng, kỳ vọng đi vào 1. Như B đi đến vô cùng, kỳ vọng đi đến vô cùng.)

Lấy mẫu một danh sách

phương pháp khác là để tạo ra một danh sách L của tất cả các giá trị được phép của bạn, sau đó lấy mẫu L[rand(L.count)].

Answer 2

Tôi giả sử bạn biết cách tạo số ngẫu nhiên trong [1, n] và danh sách của bạn cũng được sắp xếp như trong ví dụ trên.

Giả sử bạn có danh sách có phần tử k. Tạo cấu trúc bản đồ (O (logn)), sẽ đảm bảo tốc độ nếu k tăng cao hơn. Đặt tất cả các phần tử từ danh sách trong bản đồ, trong đó giá trị phần tử sẽ là khóa và giá trị "tốt" sẽ là giá trị. Sau đó tôi sẽ giải thích về giá trị "tốt". Vì vậy, khi chúng tôi có bản đồ thì chỉ cần tìm một số ngẫu nhiên trong [1, n - k - p) (Sau này tôi sẽ giải thích p là gì) và nếu số này nằm trong bản đồ thì hãy thay thế bằng giá trị "tốt".

Giá trị "TỐT" -> Hãy bắt đầu từ phần tử thứ k. Đó là giá trị tốt là giá trị riêng của nó + 1, bởi vì yếu tố tiếp theo là "tốt" cho chúng ta. Bây giờ chúng ta hãy xem xét (k-1) phần tử thứ. Chúng tôi giả định rằng giá trị tốt của nó lại là giá trị riêng của nó + 1. Nếu giá trị này bằng với phần tử thứ k thì giá trị "tốt" cho (k-1) thứ k là giá trị "tốt" thứ k + 1. bạn sẽ phải lưu trữ giá trị "tốt" lớn nhất. Nếu giá trị lớn nhất vượt quá n thì p (từ trên cao) sẽ là p = lớn nhất - n.

Tất nhiên tôi khuyên bạn chỉ nên thực hiện điều này nếu k là số lớn nếu không phương pháp @Timothy Shields là hoàn hảo.

Answer 3

Kỹ thuật tôi thường sử dụng khi danh sách là chiều dài 1 là để tạo ra một ngẫu nhiên nguyên r trong [1,n-1], và nếu r là lớn hơn hoặc bằng giá trị mà đơn bất hợp pháp sau đó tăng r.

Điều này có thể được tổng quát cho danh sách chiều dài k cho số k nhỏ nhưng yêu cầu phân loại danh sách đó (bạn không thể so sánh và tăng theo thứ tự ngẫu nhiên). Nếu danh sách dài vừa phải, sau đó sau khi sắp xếp, bạn có thể bắt đầu bằng bsearch và thêm số lượng giá trị được bỏ qua vào r và sau đó chuyển vào phần còn lại của danh sách.

Đối với một danh sách dài k, không chứa giá trị lớn hơn hoặc bằng n-k, bạn có thể làm một thay trực tiếp hơn: tạo ra ngẫu nhiên r trong [1,n-k], và sau đó lặp qua các thử nghiệm danh sách nếu r bằng list[i]. Nếu đó là thì đặt r thành n-k+i (giả định này là list là không dựa trên số 0) và thoát.

Cách tiếp cận thứ hai không thành công nếu một số phần tử danh sách nằm trong số [n-k,n].

tôi có thể cố gắng đầu tư một cái gì đó thông minh vào thời điểm này, nhưng những gì tôi có cho đến nay dường như đủ để phân phối đều liên tục với giá trị của k nhiều ít hơn n ...

1. Tạo hai danh sách - một trong các giá trị bất hợp pháp bên dưới n-k và các giá trị còn lại (điều này có thể được thực hiện tại chỗ).
2. Tạo ngẫu nhiên r trong [1,n-k]
3. Áp dụng các phương pháp thay thế trực tiếp cho danh sách đầu tiên (nếu r là list[i] sau đó thiết lập r để n-k+i và đi đến bước 5).
4. Nếu r không bị thay đổi ở bước 3 thì chúng tôi đã hoàn tất.
5. Sắp xếp danh sách các giá trị lớn hơn và sử dụng phương pháp so sánh và tăng dần.

Quan sát:

• Nếu tất cả các giá trị trong một danh sách thấp hơn, sẽ không có loại vì không có gì để sắp xếp được.
• Nếu tất cả các giá trị nằm trong danh sách trên, sẽ không có loại nào vì không có sự kiện nào trên đó r được di chuyển vào khu vực nguy hiểm.
• Làm cách tiếp cận kn, kích thước tối đa của danh sách trên (được sắp xếp) tăng lên.
• Đối với một số k, nếu có nhiều giá trị xuất hiện trong danh sách trên (loại càng lớn), cơ hội nhận được lần truy cập trong danh sách thấp hơn sẽ giảm, giảm khả năng cần sắp xếp.

Sàng lọc: Rõ ràng mọi thứ trở nên rất sorty cho lớn k, nhưng trong những trường hợp như vậy danh sách này có tương đối ít lỗ vào đó r được phép định cư. Điều này chắc chắn có thể được khai thác.

Tôi có thể đề xuất điều gì đó khác nếu có nhiều giá trị ngẫu nhiên với cùng một danh sách và giới hạn là cần thiết. Tôi hy vọng rằng danh sách các giá trị bất hợp pháp không phải là danh sách kết quả của các cuộc gọi trước đó đến chức năng này, bởi vì nếu đó là bạn sẽ không muốn bất kỳ điều này - thay vào đó bạn sẽ muốn một shuffle Fisher-Yates.

Answer 4

Lấy mẫu từ chối sẽ đơn giản nhất nếu có thể như được mô tả. Tuy nhiên, nếu bạn không muốn sử dụng điều đó, bạn có thể chuyển đổi phạm vi và giá trị không được phép thành bộ và tìm sự khác biệt. Sau đó, bạn có thể chọn một giá trị ngẫu nhiên trong số đó.

Giả sử bạn muốn phạm vi nằm trong [1, n] nhưng không ở [i, j] và bạn muốn phân phối đồng đều.

Trong Python

total = range(1,n+1) 
disallowed = range(i,j+1) 
allowed = list(set(total) - set(disallowed)) 

return allowed[random.randrange(len(allowed))] 

(Lưu ý rằng đây không phải là CHÍNH XÁC thống nhất vì trong tất cả các likeliness, max_rand%len(allowed) != 0 nhưng ý chí này trong ứng dụng thực tế nhất là rất gần)