Using Numpy to generate random combinations from two arrays without repeating

Question

For two arrays, for example [0,0,0] and [1,1,1] , it is already clear (see here ) how to generate all combinations, i.e. [[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 or product ) and numpy.meshgrid are the most common ways as far as I know.

However, I could not find a discussion on how to create these combinations randomly, without repetition.

A simple solution may be to generate all the combinations and then select some of them randomly. For instance:

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

However, this is unacceptable when the number of combinations is too large.

Is there a way to generate random combinations without replacement in Python (possibly with Numpy) without generating all combinations?

EDIT . In the accepted answer, you can notice that we also have a free way to generate random binary vectors without repetition , which is just one line (described in the "Bonus" section).

Answer 1

Here's a vector approach without generating all the combinations -

 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] 

Note that this assumes that we are dealing with an equal number of elements per group.

Explanation

To give him some clarification, let's say that the groups are stored in a 2D array -

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

We have two members per group. Let's say we are looking for 4 unique group combinations: N = 4 . To choose from two numbers from each of these three groups, we will have only 8 unique combinations.

Let it generate N unique numbers in this interval 8 , using 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]) 

Then, convert them to binary equivalents, since later we need the ones that will be indexed on each line 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]]) 

Finally, with fancy indexing, we get these elements A -

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

Run example

 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 Section

Explanation at ((dec_idx[:,None] & (1 << np.arange(m)))!=0).astype(int) :

This step basically converts decimal numbers to binary equivalents. Let it be broken down into smaller steps for a closer look.

1) The input array of decimal numbers -

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

2) Convert to 2D when inserting a new axis using None/np.newaxis -

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

3) Suppose that m = 3 , that is, we want to convert to 3 equivalents of binary numbers.

We create an array of 2-powered array with bit shift operation -

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

Alternatively, explicitly would be -

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

4) Now, the essence of the mysterious step is there. We perform a broadcasted bitwise AND-ind between a 2D dec_idx and a 2-powered range array.

Consider the first element from dec_idx : 7 . We are performing bitiwse AND-IN 7 in relation to 1 , 2 , 4 . Think of it as a filtering process, as we filter 7 in each binary interval 1 , 2 , 4 , since they represent three binary digits. Similarly, we do this for all dec_idx elements dec_idx vectorized way with broadcasting .

Thus, we get bitwise And-results, for example:

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

The filtered numbers obtained in this way are either 0 or the array numbers of the 2-powered range. So, to have binary equivalents, we just need to consider all non-zeros as 1s and zeros as 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]]) 

So we have binary numbers with MSB on the right.