使用Numpy生成兩個數組的隨機組合，無需重複

Question

給定兩個數組，例如[0,0,0]和[1,1,1]，已經清楚（見here）如何生成所有組合，即[[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或product）和numpy.meshgrid是最常用的方法。

但是，我無法找到關於如何隨機產生這些組合的討論，而沒有重複。

一個簡單的解決方案可以是生成所有的組合，然後隨機選擇其中的一些。例如：

# 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),:] 

但是，當組合數量太大時，這是不可行的。

有沒有辦法在沒有生成所有組合的情況下在Python中生成隨機組合（可能與Numpy）？

編輯：您可以接受的答案，我們也得到了一個免費的技術產生隨機二進制矢量不重複，這僅僅是一個單一的線（在獎金部分描述）的通知。

Answer 1

這裏有一個量化的方法，而不會產生所有的組合 -

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] 

請注意，這是假定我們正在處理同等數量的每組元素。

說明

給它一些解釋，讓我們假設組存儲在一個2D陣列 -

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

我們有每個組的兩個elems的。假設我們正在尋找4獨特的組合組合：N = 4。要從這三個組中的每個組中選擇兩個數字，我們將總共有8個獨特組合。

讓我們使用np.random.choice(8, N, replace=False)產生的8該區間N唯一號碼 -

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

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

然後轉換那些二進制等效爲稍後我們需要那些索引到的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]]) 

最後，用花式索引，我們得到這些elem關A -

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

樣品運行

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]]) 

---

加成部

說明上((dec_idx[:,None] & (1 << np.arange(m)))!=0).astype(int)：

即步驟基本上是轉換的十進制數爲二進制等同物。讓我們將其細分爲更小的步驟以便仔細觀察。

1）十進制數的輸入數組 -

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

2）轉換在與None/np.newaxis插入新的軸2D -

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

3）假設m = 3，也就是說，我們要轉換到3個二進制數字等值。

我們創建2-powered範圍陣列比特移位操作 -

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

可選擇地，顯式方法是 -

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

4）現在，隱蔽步驟那裏的關鍵。我們在2Ddec_idx和2-powered範圍數組之間執行broadcasted按位AND-ind。

考慮從dec_idx的第一個元素：7。我們正在針對1,2,4進行7的bitiwse AND-ing。將其視爲一個過濾過程，因爲我們在1,2,4的每個二進制間隔上過濾7，因爲它們表示三個二進制數字。同樣，我們以broadcasting的矢量化方式對dec_idx的所有元件執行此操作。

因此，我們將得到像這樣的逐位AND-ING結果 -

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

由此獲得的過濾號碼或者0或2-powered範圍陣列數字本身。因此，爲了獲得二進制等值，我們只需要考慮所有非零作爲1s和零作爲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]]) 

因此，我們有右邊的MSBs的二進制數字。