python: lấy mẫu mà không cần thay thế từ lưới 2D

Question

Tôi cần mẫu, không cần thay thế, trong số tất cả các số có thể có từ số range(n). Tức là, tôi có một tập hợp gồm (0,0), (0,1), ..., (0, n), (1,0), (1,1), ..., (1, n), ..., (n, 0), (n, 1), (n, n) và tôi đang cố gắng lấy mẫu k của các phần tử đó. Tôi hy vọng tránh việc xây dựng bộ sưu tập này một cách rõ ràng.

Tôi biết random.sample(range(n), k) rất đơn giản và hiệu quả nếu tôi cần mẫu từ một chuỗi số thay vì số lượng các số.

Tất nhiên, tôi có thể xây dựng danh sách chứa tất cả các nhóm có thể (n * n = n^2) một cách rõ ràng và sau đó gọi random.sample. Nhưng điều đó có lẽ không hiệu quả nếu k nhỏ hơn nhiều so với n^2.

Tôi không chắc liệu mọi thứ có hoạt động giống nhau trong Python 2 và 3 về hiệu quả hay không; Tôi sử dụng Python 3.

Answer 1

Tùy thuộc vào số lượng bạn đang chọn, có thể đơn giản nhất là theo dõi những thứ bạn đã chọn (qua số set) và sau đó chọn lại cho đến khi bạn nhận được thứ gì đó mà bạn chưa chọn.

Các tùy chọn khác là chỉ cần sử dụng một số toán học đơn giản:

numbers_in_nxn = random.sample(range(n*n), k) # Use xrange in Python 2.x 
tuples_in_nxn = [divmod(x,n) for x in numbers_in_nxn] 

Answer 2

Nếu không cố gắng (không python trong tầm tay):

random.shuffle(range(n))[:k] 

xem ý kiến. Đã không ngủ đủ ...

Answer 3

Bạn nói:

Tất nhiên, tôi rõ ràng có thể xây dựng danh sách chứa tất cả có thể (n * n = n^2) tuples, và sau đó gọi mẫu thử ngẫu nhiên. Nhưng điều đó có thể là không hiệu quả nếu k nhỏ hơn nhiều so với n^2.

Vâng, làm thế nào để xây dựng bộ tẩu sau bạn đã chọn ngẫu nhiên một? Tức là, nếu bạn có thể xây dựng các bộ tuple trước khi bạn chọn ngẫu nhiên cái nào để chọn, bạn có thể chọn cái đầu tiên và xây dựng sau.

Tôi không hiểu làm thế nào các bộ của bạn có nghĩa vụ phải nhìn, nhưng đây là một ví dụ, mặc dù tôi nhận ra các bộ của bạn được tất cả các chiều dài tương tự, điều này cho thấy các nguyên tắc:

Thay vì làm điều này:

>>> import random 
>>> all_sequences = [range(x) for x in range(10)] 
>>> all_sequences 
[[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8]] 
>>> random.sample(all_sequences, 3) 
[[0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6, 7, 8]] 

bạn sẽ làm điều này:

>>> import random 
>>> selection = random.sample(range(10), 3) 
>>> [range(x) for a in selection] 
[[0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8]]