मैं दो स्ट्रिंग्स (रिकर्सन के बिना) के अनन्य क्रमपरिवर्तन कैसे बना सकता हूं या बना सकता हूं

Question

प्रश्न दो दिए गए तारों के सभी संभावित अंतःक्रियाओं को मुद्रित करना है। इसलिए मैं अजगर में एक काम कोड है जो इस तरह से चलाता है ने लिखा है:

def inter(arr1,arr2,p1,p2,arr): 
    thisarr = copy(arr) 
    if p1 == len(arr1) and p2 == len(arr2): 
     printarr(thisarr) 
    elif p1 == len(arr1): 
     thisarr.extend(arr2[p2:]) 
     printarr(thisarr) 
    elif p2 == len(arr2): 
     thisarr.extend(arr1[p1:]) 
     printarr(thisarr) 
    else: 
     thisarr.append(arr1[p1]) 
     inter(arr1,arr2,p1+1,p2,thisarr) 
     del thisarr[-1] 
     thisarr.append(arr2[p2]) 
     inter(arr1,arr2,p1,p2+1,thisarr) 
    return 

यह एक स्ट्रिंग में प्रत्येक बिंदु पर आता है तो एक पुनरावर्ती कॉल के लिए, यह पहली सरणी से संबंधित के रूप में वर्तमान तत्व मानता है, और में अगली कॉल, अन्य सरणी से संबंधित है। तो अगर इनपुट तार ab और cd हैं, यह बाहर प्रिंट abcd, acbd, cdab, cabd, आदि p1 और p2 सरणियों के संकेत दिए गए हैं (क्योंकि अजगर तार अपरिवर्तनीय हैं, मैं सरणियों उपयोग कर रहा हूँ!)। क्या कोई मुझे बता सकता है, इस कोड की जटिलता क्या है, और यदि इसे बेहतर किया जा सकता है या नहीं? मैं किसी दिए गए सरणी से लंबाई k के सभी संयोजनों मुद्रित करने के लिए इसी तरह की एक कोड लिखा है:

def kcomb(arr,i,thisarr,k): 
    thisarr = copy(thisarr) 
    j,n = len(thisarr),len(arr) 
    if n-i<k-j or j >k: 
     return 
    if j==k: 
     printarr(thisarr) 
     return 
    if i == n: 
     return 
    thisarr.append(arr[i]) 
    kcomb(arr,i+1,thisarr,k) 
    del thisarr[-1] 
    kcomb(arr,i+1,thisarr,k) 
    return 

यह भी एक ही सिद्धांत पर काम करता है। तो सामान्य रूप से, ऐसे कार्यों की जटिलता कैसे प्राप्त करें, और मैं उन्हें कैसे अनुकूलित करूं? क्या डीपी द्वारा ऐसा करना संभव है? पहली समस्या के लिए नमूना इनपुट आउटपुट:

>>> arr1 = ['a','b','c'] 
>>> arr2 = ['d','e','f'] 
>>> inter(arr1,arr2,0,0,[]) 
abcdef 
abdcef 
abdecf 
abdefc 
adbcef 
adbecf 
adbefc 
adebcf 
adebfc 
adefbc 
dabcef 
dabecf 
dabefc 
daebcf 
daebfc 
daefbc 
deabcf 
deabfc 
deafbc 
defabc 

Answer 1

आपकी समस्या एक विशेष सूची के सभी अद्वितीय क्रमपरिवर्तन बनाने की है कि कम किया जा सकता। A और B क्रमशः arr1 और arr2 तारों की लंबाई हैं। तो फिर इस तरह की एक सूची का निर्माण:

[0] * A + [1] * B 

इस सूची की अनूठी क्रमपरिवर्तन से एक एक-से-एक पत्राचार (एक द्विभाजन) दो तार arr1 और arr2 के सभी संभव interleavings मौजूद है। विचार क्रमपरिवर्तन के प्रत्येक मान को निर्दिष्ट करने के लिए है कि कौन सी स्ट्रिंग से अगले अक्षर को लेना है। यहाँ एक उदाहरण है कि कैसे एक क्रमचय से एक इंटरलिविंग के निर्माण के लिए दिखा दिया गया है:

>>> def make_interleave(arr1, arr2, permutation): 
...  iters = [iter(arr1), iter(arr2)] 
...  return "".join(iters[i].next() for i in permutation) 
... 
>>> make_interleave("ab", "cde", [1, 0, 0, 1, 1]) 
'cabde' 

मैं अजगर मेलिंग सूची जो कि कैसे एक कुशल तरीके से इस समस्या को हल करने के लिए पूछता में this सवाल पाया। उत्तर एक एल्गोरिदम का उपयोग करने का सुझाव देते हैं जो Knuth के में आर्ट ऑफ कंप्यूटर प्रोग्रामिंग, वॉल्यूम 4, फास्किकल 2: सभी क्रमपरिवर्तन उत्पन्न करना है। मुझे here ड्राफ्ट का ऑनलाइन पीडीएफ मिला। इस wikipedia article में एल्गोरिदम का भी वर्णन किया गया है।

यहां एक पाइथन जनरेटर फ़ंक्शन के रूप में next_permutation एल्गोरिदम का अपना एनोटेटेड कार्यान्वयन है।

def unique_permutations(seq): 
    """ 
    Yield only unique permutations of seq in an efficient way. 

    A python implementation of Knuth's "Algorithm L", also known from the  
    std::next_permutation function of C++, and as the permutation algorithm 
    of Narayana Pandita. 
    """ 

    # Precalculate the indices we'll be iterating over for speed 
    i_indices = range(len(seq) - 1, -1, -1) 
    k_indices = i_indices[1:] 

    # The algorithm specifies to start with a sorted version 
    seq = sorted(seq) 

    while True: 
        yield seq 

     # Working backwards from the last-but-one index,          k 
        # we find the index of the first decrease in value.  0 0 1 0 1 1 1 0 
        for k in k_indices: 
            if seq[k] < seq[k + 1]: 
                break 
        else: 
      # Introducing the slightly unknown python for-else syntax: 
      # else is executed only if the break statement was never reached. 
      # If this is the case, seq is weakly decreasing, and we're done. 
            return 

     # Get item from sequence only once, for speed 
        k_val = seq[k] 

        # Working backwards starting with the last item,        k     i 
        # find the first one greater than the one at k    0 0 1 0 1 1 1 0 
        for i in i_indices: 
            if k_val < seq[i]: 
                break 

        # Swap them in the most efficient way 
        (seq[k], seq[i]) = (seq[i], seq[k])            #       k     i 
                                              # 0 0 1 1 1 1 0 0 

     # Reverse the part after but not       k 
     # including k, also efficiently.      0 0 1 1 0 0 1 1 
     seq[k + 1:] = seq[-1:k:-1] 

एल्गोरिथ्म के प्रत्येक उपज this प्रश्न के अनुसार, हे (1) के एक परिशोधित जटिलता है, लेकिन rici जो नीचे टिप्पणी की के अनुसार, यह केवल मामला है, तो सभी नंबरों को अद्वितीय हैं, जो वे निश्चित रूप से कर रहे हैं इस मामले में नहीं।

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

 
(A + B)!/(A! * B!) 

दिया जाता है क्रमपरिवर्तन के आधार पर परिणामस्वरूप स्ट्रिंग बनाने की जटिलता के साथ। यदि हम उपर्युक्त सूत्र के साथ इस योग को गुणा करते हैं तो हमें कुल समय जटिलता मिलती है।

Answer 2

क्या permutations आपके लिए काम करता है? या, यह कोडिंग अभ्यास है?

>>> from itertools import permutations 
>>> s1 = "ab" 
>>> s2 = "cd" 
>>> all_values = [c for c in s1 + s2] 
>>> ["".join(r) for r in permutations(all_values)] 
['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba'] 

Answer 3

यह है कि मैं क्या लगता है कि तुम क्या करने की कोशिश कर रहे हैं:

from itertools import product, chain 

def interleave(a, b): 
    if len(b) > len(a): 
     a, b = b, a 

    boolean = (True, False) 
    for z in range(len(a) - len(b) + 1): 
     pairs = list(zip(a[z:], b)) 
     for vector in product(*[boolean] * max(map(len, (a, b)))): 
      permutation = (pair if i else reversed(pair) 
          for i, pair in zip(vector, pairs)) 
      yield a[:z] + ''.join(chain.from_iterable(permutation)) 

Answer 4

ठीक है, कुछ काम के बाद, और अन्य उत्तरों से सलाह तैयार करें। मुख्य रूप से आलसी। (और अब एक वर्ग में परिवर्तित कर दिया है) __all_perms से है:

>>> A = ['a', 'b', 'c'] 
>>> B = ['d', 'e', 'f'] 
>>> Interleave(A, B) 
['abcdef', 'abdcef', 'abdecf', 'abdefc', 'adbcef', 'adbecf', 'adbefc', 'adebcf', 'adebfc', 'adefbc', 'dabcef', 'dabecf', 'dabefc', 'daebcf', 'daebfc', 'daefbc', 'deabcf', 'deabfc', 'deafbc', 'defabc'] 

भी

आप की तरह कक्षा के सदस्यों तक पहुँच सकते हैं: https://stackoverflow.com/a/104436/1561176

class Interleave(): 

    def __init__(self, A, B): 
     self.A = A 
     self.B = B 
     self.results = list(self.__interleave()) 

    # from https://stackoverflow.com/a/104436/1561176 
    def __all_perms(self, elements): 
     if len(elements) <=1: 
      yield elements 
     else: 
      for perm in self.__all_perms(elements[1:]): 
       for i in range(len(elements)): 
        #nb elements[0:1] works in both string and list contexts 
        yield perm[:i] + elements[0:1] + perm[i:] 

    def __sequences(self): 
     return list(sorted(set(
      ["".join(x) for x in self.__all_perms(['a'] * len(self.A) + ['b'] * len(self.B))]))) 

    def __interleave(self): 
     for sequence in self.__sequences(): 
      result = "" 
      a = 0 
      b = 0 
      for item in sequence: 
       if item == 'a': 
        result+=self.A[a] 
        a+=1 
       else: 
        result+=self.B[b] 
        b+=1 
      yield result 

    def __str__(self): 
     return str(self.results) 

    def __repr__(self): 
     return repr(self.results) 

और यहाँ उपयोग है

>>> inter = Interleave(A, B) 
>>> inter.results 
['abcdef', 'abdcef', 'abdecf', 'abdefc', 'adbcef', 'adbecf', 'adbefc', 'adebcf', 'adebfc', 'adefbc', 'dabcef', 'dabecf', 'dabefc', 'daebcf', 'daebfc', 'daefbc', 'deabcf', 'deabfc', 'deafbc', 'defabc'] 
>>> inter.A 
['a', 'b', 'c'] 
>>> inter.B 
['d', 'e', 'f']