Korzystanie Numpy generować losowe kombinacje dwóch tablic bez powtórzeń

Question

otrzymuje dwie tablice, na przykład [0,0,0] i [1,1,1], jest już jasne (patrz here) jak wygenerować wszystkie kombinacje, tj [[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 lub product) i numpy.meshgrid są najczęstszymi sposobami, o ile wiem.

Jednak nie mogłem znaleźć żadnych dyskusji na temat generowania tych kombinacji losowo, bez powtórzeń.

Łatwe rozwiązanie może polegać na generowaniu wszystkich kombinacji, a następnie losowaniu niektórych z nich. Na przykład:

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

Jest to jednak niewykonalne, gdy liczba kombinacji jest zbyt duża.

Czy istnieje sposób generowania losowych kombinacji bez zamiany w Pythonie (ewentualnie z Numpy) bez generowania wszystkich kombinacji?

EDIT: Można zauważyć w przyjętym odpowiedzi, które dostaliśmy również za darmo techniki generowania losowych wektorów binarnych bez powtórzeń, który jest tylko jedna linia (opisane w sekcji Bonus).

Answer 1

Oto Vectorized podejścia bez generowania wszystkie kombinacje -

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] 

Należy pamiętać, że zakłada to mamy do czynienia z taką samą liczbę elementów w grupie.

Wyjaśnienie

dać mu trochę wyjaśnienia, powiedzmy, że grupy są przechowywane w tablicy 2D -

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

Mamy dwa elems każdej grupie. Załóżmy, że szukamy 4 unikalnych kombinacji grup: N = 4. Aby wybrać spośród dwóch liczb z każdej z tych trzech grup, w sumie mamy unikalne kombinacje 8.

Niech generować N unikalnych numerów w tym przedziale 8 użyciu 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]) 

Następnie przekonwertować te do ekwiwalentów binarnych jak później musimy ci do indeksu w każdym rzędzie 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]]) 

Wreszcie, dzięki fantazyjnemu indeksowaniu, otrzymujemy te elemy od A -

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

przebiegu próbki

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 sekcja

Wyjaśnienie na ((dec_idx[:,None] & (1 << np.arange(m)))!=0).astype(int):

Ten etap jest w zasadzie konwersji liczb dziesiętnych równoważników binarnych. Podzielmy go na mniejsze kroki, aby bliżej się przyjrzeć.

1) tablica Wprowadzanie liczb dziesiętnych -

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

2) Konwersja do 2D po włożeniu nowej osi z None/np.newaxis -

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

3) Załóżmy m = 3, czyli chcemy przekonwertować 3 binarne liczby cyfrowe.

Tworzymy 2-powered zakres tablicę z operacji bit-shift -

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

Alternatywnie wyraźny sposób byłoby -

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

4) Teraz sedno tajemniczym kroku tam. Wykonujemy broadcasted bitowo AND-ind pomiędzy tablicami zakresów 2Ddec_idx i 2-powered.

Rozważ pierwszy element z dec_idx: 7. Wykonujemy bitowe przekształcanie AND-ing o wartości 7 przeciwko 1, 2, 4. Pomyśl o tym jako o procesie filtrowania, ponieważ filtrujemy 7 w każdym dwuskładnikowym przedziale 1, 2, 4, ponieważ reprezentują one trzy cyfry binarne. Podobnie robimy to dla wszystkich elemów z dec_idx w wektorze z broadcasting.

Zatem chcielibyśmy uzyskać wyniki bitową I-ing jak tak -

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

Przefiltrowane numery otrzymane w ten sposób są albo 0 lub 2-powered zakres tablicy same numery.Tak więc, aby mieć binarne odpowiedniki, musimy po prostu wziąć pod uwagę wszystkie niezerowe zerki jako 1s i zera jako 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]]) 

Tak więc mamy liczby binarne z MSB po prawej stronie.