2013-02-26 2 views
6

का उपयोग करके सेट का क्रॉस उत्पाद मैंने दो सेटों के क्रॉस उत्पाद की गणना करने के लिए निम्नलिखित रिकर्सिव रूटीन लिखा है।रिकर्सन

def combine(input1,input2,output): 
    if len(input2)==0: 
     return output 
    else: 
     for num in input1: 
      output.append((num,input2[0])) 
     combine(input1,input2[1:],output) 

input1=[1 2 5] 
input2=[2 3] 
output=[(1,2), (1,3), (2,2),(2,3),(5,2),(5,3)] 

यह संभव किसी और में पाश को दूर करने और एक ही समारोह में क्या करने की कोशिश कर उदाहरण के लिए प्रत्यावर्तन बेहतर बनाने के लिए, है। मैं समस्या को हल करने के विभिन्न तरीकों को देख रहा हूं।

संपादित करें: कुछ अंतर्निहित समाधान के साथ समाधान की तलाश नहीं है। मैं अलग-अलग रिकर्सन कैसे कर सकता हूं, और itertools.product का उपयोग नहीं कर रहा हूं।

+3

क्या आप 'itertools.product' के बारे में जानते हैं? –

+0

@LevLevitsky मेरा बुरा, प्रश्न संपादित किया – gizgok

+0

मुझे लगता है कि आपके अंतिम 'गठबंधन' कॉल के सामने 'वापसी' की आवश्यकता है। – DSM

उत्तर

2

उपयोग itertools

import itertools 

print list(itertools.product(input1, input2)) 

शब्दार्थ इस के बराबर है:

for i_1 in input_1: 
    for i_2 in input_2: 
     for i_3 in input_3: 
      ... 
       for i_n in input_n: 
        #do something with i_1, i_2, i_3, ..., i_n 

जहाँ n तर्क आप product को पारित की संख्या है।

+2

यह पूरी तरह से ओपी के बिंदु को याद करता है, जो रिकर्सन को बेहतर बनाने के लिए है। – tacaswell

+0

@tcaswell: निष्पक्ष होने के लिए, मूल संस्करण ने कहा, "मैं समस्या को हल करने के विभिन्न तरीकों को देख रहा हूं" और इसमें अंतिम पैराग्राफ नहीं था, इसलिए उस समय यह समझ में आया। – DSM

7

कार्टेशियन उत्पाद की सबसे सरल पुनरावर्ती परिभाषा मैं इस तरह दिखने के बारे में सोच सकता हूं। आप इसे अपने जैसे देख सकते हैं, इसमें एक लूप है - असल में, एक सूची समझ में एम्बेडेड दो लूप। तुम्हारा के विपरीत, इस दो या अधिक दृश्यों को संभाल कर सकते हैं:

def product(*seqs): 
    if not seqs: 
     return [[]] 
    else: 
     return [[x] + p for x in seqs[0] for p in product(*seqs[1:])] 

यहाँ आप यह कैसे काम करता की भावना देने के लिए माध्यम से गुजरने के है। परिभाषा के अनुसार, खाली अनुक्रम का कार्टेशियन उत्पाद (product()) एक अनुक्रम है जिसमें खाली अनुक्रम होता है। दूसरे शब्दों में, product() == [[]] - see here क्यों।

अब मान लें कि हम product([1, 2, 3]) - seqs पर कॉल नहीं करते हैं, इसलिए वापसी मूल्य सूची समझ का परिणाम है। इस मामले में, product(*seqs[1:]) == product(*[]) == product() == [[]], तो सूची समझ इस के बराबर है:

[[x] + p for x in seqs[0] for p in [[]] ] 

जो इन सभी के बराबर है:

[[x] + [] for x in seqs[0]] 
[[x] for x in seqs[0]] 
[[1], [2], [3]] 

एक और अनुक्रम जोड़ा जा रहा है, हमारे पास product([4, 5, 6], [1, 2, 3]) है। अब सूची समझ इस तरह दिखती है:

[[x] + p for x in [4, 5, 6] for p in product(*seqs[1:])] 
[[x] + p for x in [4, 5, 6] for p in [[1], [2], [3]]] 
[[4, 1], [4, 2], [4, 3], [5, 1], [5, 2], [5, 3], [6, 1], [6, 2], [6, 3]] 

पैटर्न वहां से जारी है; प्रत्येक अतिरिक्त अनुक्रम के लिए, अनुक्रम में प्रत्येक मान निम्नलिखित अनुक्रमों के कार्टेशियन उत्पाद में प्रत्येक मान के लिए तैयार किया जाता है।

+0

इसके लिए धन्यवाद। मैंने आपके मनोरंजन के लिए [+ststoverflow.com/a/29654551/1774667) अपने कार्यान्वयन के लिए सी ++ में एक संकलित समय क्रॉस उत्पाद करने के लिए आपके कार्यान्वयन का उपयोग किया। – Yakk

संबंधित मुद्दे