, पुनरावृत्ति

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]] Numpy का उपयोग करना। 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),:] 

हालांकि, यह असुरक्षित है जब संयोजनों की संख्या बहुत बड़ी है।

क्या सभी संयोजनों को उत्पन्न किए बिना पाइथन (संभवतः नम्पी के साथ) के बिना यादृच्छिक संयोजन उत्पन्न करने का कोई तरीका है?

संपादित: आप स्वीकार किए जाते हैं जवाब यह है कि हम भी मुक्त एक तकनीक है जिसके सिर्फ एक लाइन (बोनस धारा में वर्णित) है repetitions बिना यादृच्छिक द्विआधारी वैक्टर, उत्पन्न करने के लिए के लिए मिल गया में नोटिस कर सकते हैं।

Answer 1

यहाँ सभी संयोजनों पैदा करने के बिना एक vectorized दृष्टिकोण है -

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 अद्वितीय संयोजन होंगे।तब

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

के np.random.choice(8, N, replace=False) का उपयोग कर 8 की कि अंतराल में N अद्वितीय नंबर जेनरेट करते हैं

अंत में, फैंसी-इंडेक्सिंग के साथ, हम उन एम्स को A -

से प्राप्त करते हैं

नमूना रन

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 बाइनरी अंक संख्या समकक्ष।

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) अब, वहाँ गुप्त कदम की जड़

हम थोड़ा-शिफ्ट संचालन के साथ 2-powered रेंज सरणी पैदा करते हैं। हम broadcasted बिटवाई और 2Ddec_idx और 2-powered रेंज सरणी के बीच प्रदर्शन करते हैं।

dec_idx: 7 से पहले तत्व पर विचार करें। हम 7 के 1, 2, 4 के विरुद्ध 7 के बिटकवे एंड-आईएनजी कर रहे हैं। इसे फ़िल्टरिंग प्रक्रिया के रूप में सोचें, क्योंकि हम , 2, 4 के प्रत्येक बाइनरी अंतराल पर 7 फ़िल्टर करते हैं क्योंकि वे तीन बाइनरी अंकों का प्रतिनिधित्व करते हैं। इसी तरह, हम dec_idx से broadcasting के साथ वेक्टरकृत तरीके से सभी एम्स के लिए ऐसा करते हैं।

इस प्रकार, हम मिलेगा बिट के लिहाज से और-आईएनजी परिणाम इतने तरह -

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

इस प्रकार, हमारे पास एमएसबी के साथ द्विआधारी संख्याएं हैं।