Chọn N mục ngẫu nhiên từ chuỗi có độ dài không xác định

Question

Tôi đang cố gắng viết một thuật toán có thể chọn N mục riêng biệt từ một chuỗi ngẫu nhiên mà không biết kích thước của chuỗi trước. trình tự nhiều lần. Ví dụ, các phần tử của chuỗi có thể là các dòng của một tệp lớn.

Tôi đã tìm thấy một giải pháp khi N = 1 (có nghĩa là, khi cố gắng chọn đúng một phần tử một cách ngẫu nhiên từ một chuỗi rất lớn):

import random 
items = range(1, 10) # Imagine this is a huge sequence of unknown length 
count = 1 
selected = None 
for item in items: 
    if random.random() * count < 1: 
     selected = item 
    count += 1 

Nhưng làm thế nào tôi có thể đạt được điều tương tự cho các giá trị khác của N (N = 3)?

Answer 1

Sử dụng reservoir sampling. Đó là một thuật toán rất đơn giản, hoạt động với bất kỳ N nào.

Here là một triển khai Python và here là một cách khác.

Answer 2

Như aix đã đề cập đến công việc lấy mẫu hồ chứa. Một tùy chọn khác là tạo một số ngẫu nhiên cho mỗi số bạn nhìn thấy và chọn số k đầu.

Để làm điều đó lặp đi lặp lại, hãy duy trì một số cặp k (số ngẫu nhiên, số) và bất cứ khi nào bạn nhìn thấy số mới chèn vào heap nếu nó lớn hơn giá trị nhỏ nhất trong heap.

Answer 3

Sẽ đủ để chấp nhận hoặc từ chối từng mục mới chỉ một lần và nếu bạn chấp nhận, hãy ném một mục cũ đã chọn ngẫu nhiên.

Giả sử bạn đã chọn ngẫu nhiên N mục K và bạn thấy mục thứ K (1). Chấp nhận nó với xác suất N/(K + 1) và xác suất của nó là OK. Các mục hiện tại có được với xác suất N/K, và được ném ra với xác suất (N/(K + 1)) (1/N) = 1/(K + 1) để tồn tại thông qua xác suất (N/K) (K/(K + 1)) = N/(K + 1) để xác suất của chúng cũng OK.

Và vâng tôi thấy ai đó đã chỉ cho bạn lấy mẫu hồ chứa - đây là một giải thích về cách thức hoạt động.

Answer 4

@NPE là chính xác, nhưng việc triển khai được liên kết là phụ tối ưu và không phải là rất "pythonic". Dưới đây là một thực hiện tốt hơn:

def sample(iterator, k): 
    """ 
    Samples k elements from an iterable object. 

    :param iterator: an object that is iterable 
    :param k: the number of items to sample 
    """ 
    # fill the reservoir to start 
    result = [next(iterator) for _ in range(k)] 

    n = k - 1 
    for item in iterator: 
     n += 1 
     s = random.randint(0, n) 
     if s < k: 
      result[s] = item 

    return result 

Sửa Như @ panda-34 chỉ ra phiên bản gốc đã được thiếu sót, nhưng không phải vì tôi đã sử dụng randint vs randrange. Vấn đề là giá trị ban đầu của tôi cho n không tính đến thực tế là randint được bao gồm trên cả hai đầu của phạm vi. Việc tính đến điều này sẽ khắc phục được sự cố. (Lưu ý: bạn cũng có thể sử dụng randrange vì nó được bao gồm trên giá trị tối thiểu và độc quyền trên giá trị tối đa.)

Answer 5

Nếu trình tự của bạn đủ ngắn để đọc nó và bộ nhớ ngẫu nhiên là chấp nhận được. nên chỉ sử dụng random.shuffle:

import random 
arr=[1,2,3,4] 

# In-place shuffle 
random.shuffle(arr) 

# Take the first 2 elements of the now randomized array 
print arr[0:2] 
[1, 3] 

Tùy thuộc vào loại chuỗi, bạn có thể cần phải chuyển đổi nó vào một danh sách bằng cách gọi list(your_sequence) vào nó, nhưng điều này sẽ làm việc không phụ thuộc vào loại các đối tượng theo thứ tự của bạn .

Đương nhiên, nếu bạn không thể phù hợp với trình tự của bạn vào bộ nhớ hoặc yêu cầu bộ nhớ hoặc CPU của phương pháp này quá cao đối với bạn, bạn sẽ cần phải sử dụng một giải pháp khác.

Answer 6

Tiếp theo sẽ cung cấp cho bạn các mặt hàng N ngẫu nhiên từ một mảng X

import random 
list(map(lambda _: random.choice(X), range(N))) 

Answer 7

Đây là câu trả lời của tôi cho một câu hỏi trùng lặp (đóng trước khi tôi có thể gửi) đó là phần nào liên quan ("tạo ra số ngẫu nhiên mà không cần bất kỳ bản sao"). Vì nó là một cách tiếp cận khác với các câu trả lời khác, tôi sẽ để nó ở đây trong trường hợp nó cung cấp cái nhìn sâu sắc hơn.

from random import randint 

random_nums = [] 
N = # whatever number of random numbers you want 
r = # lower bound of number range 
R = # upper bound of number range 

x = 0 

while x < N: 
    random_num = randint(r, R) # inclusive range 
    if random_num in random_nums: 
     continue 
    else: 
     random_nums.append(random_num) 
     x += 1 

Lý do cho vòng lặp while trong vòng lặp for là nó cho phép để thực hiện dễ dàng hơn không bỏ qua trong thế hệ ngẫu nhiên (ví dụ: nếu bạn nhận được 3 bản sao, bạn sẽ không nhận số N-3).

Answer 8

Tôi sẽ sử dụng lựa chọn

from random import choices 

items = range(1, 10) 
new_items = choices(items, k = 3) 

print(new_items) 
[6, 3, 1]