Sử dụng Numpy để tạo kết hợp ngẫu nhiên của hai mảng không lặp lại

Question

Cho hai mảng, ví dụ [0,0,0] và [1,1,1], đã rõ ràng (xem here) cách tạo tất cả các kết hợp, tức là [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]. itertools (combinations hoặc product) và numpy.meshgrid là những cách phổ biến nhất theo như tôi biết.

Tuy nhiên, tôi không thể tìm thấy bất kỳ cuộc thảo luận nào về cách tạo các kết hợp này một cách ngẫu nhiên mà không lặp lại.

Một giải pháp dễ dàng có thể là tạo tất cả các kết hợp và sau đó chọn một số ngẫu nhiên. Ví dụ:

# Three random combinations of [0,0,0] and [1,1,1] 
comb = np.array(np.meshgrid([0,1],[0,1],[0,1])).T.reshape(-1,3) 
result = comb[np.random.choice(len(comb),3,replace=False),:] 

Tuy nhiên, điều này là không khả thi khi số lượng kết hợp quá lớn.

Có cách nào để tạo các kết hợp ngẫu nhiên mà không cần thay thế bằng Python (có thể với Numpy) mà không tạo tất cả các kết hợp không?

EDIT: Bạn có thể nhận thấy trong câu trả lời chấp nhận rằng chúng tôi cũng đã cho một kỹ thuật miễn phí để tạo vectơ nhị phân ngẫu nhiên mà không lặp lại, mà chỉ là một dòng duy nhất (được mô tả trong Phần Bonus).

Answer 1

Dưới đây là một cách tiếp cận vectorized mà không tạo tất cả các kết hợp -

def unique_combs(A, N): 
    # A : 2D Input array with each row representing one group 
    # N : No. of combinations needed 
    m,n = A.shape 
    dec_idx = np.random.choice(2**m,N,replace=False) 
    idx = ((dec_idx[:,None] & (1 << np.arange(m)))!=0).astype(int) 
    return A[np.arange(m),idx] 

Xin lưu ý rằng điều này giả định chúng ta đang đối phó với số lượng tương đương của các yếu tố cho mỗi nhóm.

Giải thích

Để cung cấp cho nó một chút giải thích, giả sử các nhóm được lưu trữ trong một mảng 2D -

In [44]: A 
Out[44]: 
array([[4, 2], <-- group #1 
     [3, 5], <-- group #2 
     [8, 6]]) <-- group #3 

Chúng tôi có hai đơn vị cho mỗi nhóm. Giả sử chúng ta đang tìm kiếm 4 kết hợp nhóm duy nhất: N = 4. Để chọn từ hai số từ mỗi nhóm trong số ba nhóm này, chúng tôi sẽ có tổng cộng 8 kết hợp độc đáo.

Hãy tạo N số độc đáo ở chỗ khoảng thời gian 8 sử dụng np.random.choice(8, N, replace=False) -

In [86]: dec_idx = np.random.choice(8,N,replace=False) 

In [87]: dec_idx 
Out[87]: array([2, 3, 7, 0]) 

Sau đó, chuyển đổi những để tương đương nhị phân như sau này chúng ta cần những người đến chỉ số vào mỗi hàng của A -

In [88]: idx = ((dec_idx[:,None] & (1 << np.arange(3)))!=0).astype(int) 

In [89]: idx 
Out[89]: 
array([[0, 1, 0], 
     [1, 1, 0], 
     [1, 1, 1], 
     [0, 0, 0]]) 

Cuối cùng, với việc lập chỉ mục ưa thích, chúng tôi có được những elems đó ra khỏi A -

In [90]: A[np.arange(3),idx] 
Out[90]: 
array([[4, 5, 8], 
     [2, 5, 8], 
     [2, 5, 6], 
     [4, 3, 8]]) 

mẫu chạy

In [80]: # Original code that generates all combs 
    ...: comb = np.array(np.meshgrid([4,2],[3,5],[8,6])).T.reshape(-1,3) 
    ...: result = comb[np.random.choice(len(comb),4,replace=False),:] 
    ...: 

In [81]: A = np.array([[4,2],[3,5],[8,6]]) # 2D array of groups 

In [82]: unique_combs(A, 3) # 3 combinations 
Out[82]: 
array([[2, 3, 8], 
     [4, 3, 6], 
     [2, 3, 6]]) 

In [83]: unique_combs(A, 4) # 4 combinations 
Out[83]: 
array([[2, 3, 8], 
     [4, 3, 6], 
     [2, 5, 6], 
     [4, 5, 8]]) 

---

Bonus phần

Giải thích về ((dec_idx[:,None] & (1 << np.arange(m)))!=0).astype(int):

bước Đó là về cơ bản chuyển đổi số thập phân để tương đương nhị phân. Hãy chia nhỏ nó xuống các bước nhỏ hơn để có cái nhìn gần hơn.

1) mảng đầu vào của số thập phân -

In [18]: dec_idx 
Out[18]: array([7, 6, 4, 0]) 

2) Chuyển đổi sang 2D sau khi chèn trục mới với None/np.newaxis -

In [19]: dec_idx[:,None] 
Out[19]: 
array([[7], 
     [6], 
     [4], 
     [0]]) 

3) Giả sử m = 3, tức là chúng tôi muốn chuyển đổi sang 3 số nhị phân tương đương.

Chúng tôi tạo ra 2-powered mảng tầm hoạt động với hoạt động bit ca -

In [16]: (1 << np.arange(m)) 
Out[16]: array([1, 2, 4]) 

Ngoài ra, một cách rõ ràng sẽ là -

In [20]: 2**np.arange(m) 
Out[20]: array([1, 2, 4]) 

4) Bây giờ, mấu chốt của bước khó hiểu đó. Chúng tôi thực hiện broadcasted bitwise AND-ind giữa các mảng 2Ddec_idx và 2-powered.

Xem xét phần tử đầu tiên từ dec_idx: 7. Chúng tôi đang thực hiện bitiwse AND-ing của 7 chống lại 1, 2, 4. Hãy suy nghĩ về nó như là một quá trình lọc, khi chúng tôi lọc 7 tại mỗi khoảng thời gian nhị phân của 1, 2, 4 khi chúng đại diện cho ba chữ số nhị phân. Tương tự, chúng tôi làm điều này cho tất cả các elems ra khỏi dec_idx theo cách được vectorized với broadcasting.

Do đó, chúng tôi sẽ nhận được chút khôn ngoan VÀ-ing kết quả như vậy -

In [43]: (dec_idx[:,None] & (1 << np.arange(m))) 
Out[43]: 
array([[1, 2, 4], 
     [0, 2, 4], 
     [0, 0, 4], 
     [0, 0, 0]]) 

Các con số được lọc do đó thu được là một trong hai 0 hoặc 2-powered số mảng phạm vi bản thân.Vì vậy, để có các số nhị phân tương đương, chúng ta chỉ cần xem xét tất cả các số không là 1s và số không là 0s.

In [44]: ((dec_idx[:,None] & (1 << np.arange(m)))!=0) 
Out[44]: 
array([[ True, True, True], 
     [False, True, True], 
     [False, False, True], 
     [False, False, False]], dtype=bool) 

In [45]: ((dec_idx[:,None] & (1 << np.arange(m)))!=0).astype(int) 
Out[45]: 
array([[1, 1, 1], 
     [0, 1, 1], 
     [0, 0, 1], 
     [0, 0, 0]]) 

Vì vậy, chúng tôi có số nhị phân có MSB ở bên phải.