पाइथन itertools.permutations के लिए एल्गोरिदम

Question

क्या कोई कृपया पाइथन मानक lib 2.6 में itertools.permutations दिनचर्या के लिए एल्गोरिदम समझा सकता है? मुझे समझ में नहीं आता कि यह क्यों काम करता है।

कोड है:

def permutations(iterable, r=None): 
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    # permutations(range(3)) --> 012 021 102 120 201 210 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    if r > n: 
     return 
    indices = range(n) 
    cycles = range(n, n-r, -1) 
    yield tuple(pool[i] for i in indices[:r]) 
    while n: 
     for i in reversed(range(r)): 
      cycles[i] -= 1 
      if cycles[i] == 0: 
       indices[i:] = indices[i+1:] + indices[i:i+1] 
       cycles[i] = n - i 
      else: 
       j = cycles[i] 
       indices[i], indices[-j] = indices[-j], indices[i] 
       yield tuple(pool[i] for i in indices[:r]) 
       break 
     else: 
      return 

Answer 1

आप permutation cycles के गणितीय सिद्धांत, यह भी "ऑर्बिट्स" के रूप में जाना समझने की जरूरत है (यह गणितीय विषय के बाद से combinatorics के दिल दोनों "कला की दृष्टि से" पता करने के लिए, महत्वपूर्ण है , काफी उन्नत है, और आपको research papers देखने की आवश्यकता हो सकती है जो या तो दोनों या दोनों शर्तों का उपयोग कर सकती है)।

क्रमपरिवर्तन के सिद्धांत के लिए एक सरल परिचय के लिए, wikipedia मदद कर सकता है। मैंने जिन यूआरएल का उल्लेख किया है, उनमें से प्रत्येक उचित ग्रंथसूची प्रदान करता है यदि आप इसे और अधिक अन्वेषण करना चाहते हैं और वास्तविक समझ हासिल करना चाहते हैं (मैंने व्यक्तिगत रूप से - यह मेरे लिए शौक का कुछ हद तक बन गया है ;-)।

एक बार जब आप गणितीय सिद्धांत को समझते हैं, तो कोड "रिवर्स इंजीनियर" के लिए अभी भी सूक्ष्म और दिलचस्प है। जाहिर है, indices, बस पूल में सूचकांक के संदर्भ में वर्तमान परिवर्तन है दी झुकेंगे हमेशा से

yield tuple(pool[i] for i in indices[:r]) 

दिया जाता है आइटम तो इस आकर्षक मशीनरी के दिल cycles, जो परिवर्तन की कक्षाओं का प्रतिनिधित्व करता है और indices का कारण बनता है कि अद्यतन करने की, ज्यादातर बयानों से

j = cycles[i] 
indices[i], indices[-j] = indices[-j], indices[i] 

Ie, अगर cycles[i]j है, इसका मतलब है कि सूचकांक के बगल में अद्यतन जे-वें से एक के साथ आई-वें एक (बाएं से) स्वैप करने के लिए है से दाएं (उदाहरण के लिए, यदि j 1 है, तो indices का तत्व स्वैप किया जा रहा है - indices[-1])।

indices[i:] = indices[i+1:] + indices[i:i+1] 
cycles[i] = n - i 

यह बहुत अंत में indices की i वें आइटम डालता है, के लिए सूचकांक एक निम्न में से सभी आइटम स्थानांतरण: और फिर वहाँ लगातार कम "बहु-अपडेट" cycles के एक आइटम पर पहुंच गया जब इसके decrements दौरान 0 है बाएं, और इंगित करता है कि अगली बार जब हम cycles के इस आइटम पर आते हैं तो हम indices (बाएं से) के वें आइटम को n - i वें (दाएं से) के साथ बदल देंगे - यह i वें होगा एक बार फिर, इस तथ्य के अलावा कि

cycles[i] -= 1 

होगा

इससे पहले कि हम इसकी जांच करें ;-)।

कठिन हिस्सा निश्चित रूप से साबित कर देगा कि यह काम करता है - यानी, सभी क्रमपरिवर्तन पूरी तरह से उत्पन्न होते हैं, बिना ओवरलैप और सही ढंग से "समय" निकास के साथ। मुझे लगता है कि, एक सबूत के बजाय, यह देखना आसान हो सकता है कि सरल मामलों में पूरी तरह से उजागर होने पर मशीनरी कैसे काम करती है - yield कथनों को टिप्पणी करते हुए और print वाले (पायथन 2।*), हमारे पास

def permutations(iterable, r=None): 
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    # permutations(range(3)) --> 012 021 102 120 201 210 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    if r > n: 
     return 
    indices = range(n) 
    cycles = range(n, n-r, -1) 
    print 'I', 0, cycles, indices 
    # yield tuple(pool[i] for i in indices[:r]) 
    print indices[:r] 
    while n: 
     for i in reversed(range(r)): 
      cycles[i] -= 1 
      if cycles[i] == 0: 
     print 'B', i, cycles, indices 
       indices[i:] = indices[i+1:] + indices[i:i+1] 
       cycles[i] = n - i 
     print 'A', i, cycles, indices 
      else: 
     print 'b', i, cycles, indices 
       j = cycles[i] 
       indices[i], indices[-j] = indices[-j], indices[i] 
     print 'a', i, cycles, indices 
       # yield tuple(pool[i] for i in indices[:r]) 
      print indices[:r] 
       break 
     else: 
      return 

permutations('ABC', 2) 

चल रहा है इस से पता चलता: cycles पर

I 0 [3, 2] [0, 1, 2] 
[0, 1] 
b 1 [3, 1] [0, 1, 2] 
a 1 [3, 1] [0, 2, 1] 
[0, 2] 
B 1 [3, 0] [0, 2, 1] 
A 1 [3, 2] [0, 1, 2] 
b 0 [2, 2] [0, 1, 2] 
a 0 [2, 2] [1, 0, 2] 
[1, 0] 
b 1 [2, 1] [1, 0, 2] 
a 1 [2, 1] [1, 2, 0] 
[1, 2] 
B 1 [2, 0] [1, 2, 0] 
A 1 [2, 2] [1, 0, 2] 
b 0 [1, 2] [1, 0, 2] 
a 0 [1, 2] [2, 0, 1] 
[2, 0] 
b 1 [1, 1] [2, 0, 1] 
a 1 [1, 1] [2, 1, 0] 
[2, 1] 
B 1 [1, 0] [2, 1, 0] 
A 1 [1, 2] [2, 0, 1] 
B 0 [0, 2] [2, 0, 1] 
A 0 [3, 2] [0, 1, 2] 

फोकस: वे शुरू 3, 2 के रूप में - तो पिछले एक कम कर रहा है, इसलिए 3, 1 - आखिरी शून्य शून्य नहीं है इसलिए हमारे पास "छोटा" ईवेंट (इंडेक्स में एक स्वैप) है और आंतरिक लूप तोड़ता है। फिर हम इसे फिर से दर्ज करते हैं, इस बार अंतिम की कमी 3, 0 देती है - आखिरी अब शून्य है, इसलिए यह सूचकांक में "बड़ा" घटना - "द्रव्यमान स्वैप" है (अच्छी तरह से यहां एक द्रव्यमान नहीं है, लेकिन, हो सकता है ;-) और चक्र 3, 2 पर वापस आ गए हैं। लेकिन अब हमने लूप को तोड़ दिया नहीं है, इसलिए हम को अगले -to-last (इस मामले में, पहले) को कम करके जारी रखते हैं) - जो एक मामूली घटना देता है, सूचकांक में एक स्वैप देता है, और हम फिर भी आंतरिक लूप को तोड़ देते हैं। लूप पर वापस, फिर भी आखिरी बार कम हो गया है, इस बार 2, 1 - मामूली घटना इत्यादि दे रहा है। आखिरकार लूप के लिए एक संपूर्ण घटना केवल प्रमुख घटनाओं के साथ होती है, कोई मामूली नहीं - वह तब होता है जब चक्र सभी के रूप में शुरू होते हैं , इसलिए कमी प्रत्येक को शून्य (प्रमुख घटना) में ले जाती है, yield उस अंतिम चक्र पर होती है।

चूंकि उस चक्र में कभी भी break निष्पादित नहीं किया गया है, इसलिए हम for की शाखा लेते हैं, जो लौटाता है। ध्यान दें कि while n थोड़ा भ्रामक हो सकता है: यह वास्तव में while True - n कभी भी परिवर्तित नहीं होता है, while लूप केवल return कथन से निकलता है; n0 (खाली "पूल") के रूप में पहले, छोटे खाली yield के बाद उपज करने के लिए और कुछ भी नहीं है, इसके बाद if not n: return के बाद if not n: return के बाद इसे समान रूप से अच्छी तरह से व्यक्त किया जा सकता है। लेखक ने को while ;-) के साथ चेक करके कुछ लाइनों को सहेजने का निर्णय लिया।

मेरा सुझाव है कि आप कुछ और ठोस मामलों की जांच करके जारी रखें - अंत में आपको "घड़ी" ऑपरेटिंग को समझना चाहिए। पहले cycles पर फ़ोकस करें (शायद print बयान संपादित करें, तदनुसार indices हटाएं), क्योंकि उनकी कक्षा के माध्यम से उनकी घड़ी की तरह प्रगति इस सूक्ष्म और गहरी एल्गोरिदम की कुंजी है; एक बार आप grok कि, जिस तरह से indices ठीक से cycles के अनुक्रमण के जवाब में अपडेट कर दिया लगभग एक अवनति है -!)

Answer 2

यह शब्दों से परिणामों में एक पैटर्न के साथ जवाब देने के लिए (सिवाय आप जानना चाहते हैं आसान है सिद्धांत के गणित भाग), इसलिए प्रिंट आउट करने का सबसे अच्छा तरीका होगा।
सबसे सूक्ष्म बात यह है कि, अंत तक लूपिंग के बाद, यह स्वयं को अंतिम दौर की पहली मोड़ पर रीसेट कर देगा, और अगले लूपिंग को शुरू कर देगा, या आखिरी दौर के पहले दौर में लगातार रीसेट हो जाएगा, घड़ी की तरह

रीसेट काम कर कोड का हिस्सा:

  if cycles[i] == 0: 
      indices[i:] = indices[i+1:] + indices[i:i+1] 
      cycles[i] = n - i 

पूरे: परिणाम के

In [54]: def permutations(iterable, r=None): 
    ...:  # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    ...:  # permutations(range(3)) --> 012 021 102 120 201 210 
    ...:  pool = tuple(iterable) 
    ...:  n = len(pool) 
    ...:  r = n if r is None else r 
    ...:  if r > n: 
    ...:   return 
    ...:  indices = range(n) 
    ...:  cycles = range(n, n-r, -1) 
    ...:  yield tuple(pool[i] for i in indices[:r]) 
    ...:  print(indices, cycles) 
    ...:  while n: 
    ...:   for i in reversed(range(r)): 
    ...:    cycles[i] -= 1 
    ...:    if cycles[i] == 0: 
    ...:     indices[i:] = indices[i+1:] + indices[i:i+1] 
    ...:     cycles[i] = n - i 
    ...:     print("reset------------------") 
    ...:     print(indices, cycles) 
    ...:     print("------------------") 
    ...:    else: 
    ...:     j = cycles[i] 
    ...:     indices[i], indices[-j] = indices[-j], indices[i] 
    ...:     print(indices, cycles, i, n-j) 
    ...:     yield tuple(pool[i] for i in indices[:r]) 
    ...:     break 
    ...:   else: 
    ...:    return 

हिस्सा:

In [54]: list(','.join(i) for i in permutations('ABCDE', 3)) 
([0, 1, 2, 3, 4], [5, 4, 3]) 
([0, 1, 3, 2, 4], [5, 4, 2], 2, 3) 
([0, 1, 4, 2, 3], [5, 4, 1], 2, 4) 
reset------------------ 
([0, 1, 2, 3, 4], [5, 4, 3]) 
------------------ 
([0, 2, 1, 3, 4], [5, 3, 3], 1, 2) 
([0, 2, 3, 1, 4], [5, 3, 2], 2, 3) 
([0, 2, 4, 1, 3], [5, 3, 1], 2, 4) 
reset------------------ 
([0, 2, 1, 3, 4], [5, 3, 3]) 
------------------ 
([0, 3, 1, 2, 4], [5, 2, 3], 1, 3) 
([0, 3, 2, 1, 4], [5, 2, 2], 2, 3) 
([0, 3, 4, 1, 2], [5, 2, 1], 2, 4) 
reset------------------ 
([0, 3, 1, 2, 4], [5, 2, 3]) 
------------------ 
([0, 4, 1, 2, 3], [5, 1, 3], 1, 4) 
([0, 4, 2, 1, 3], [5, 1, 2], 2, 3) 
([0, 4, 3, 1, 2], [5, 1, 1], 2, 4) 
reset------------------ 
([0, 4, 1, 2, 3], [5, 1, 3]) 
------------------ 
reset------------------(bigger reset) 
([0, 1, 2, 3, 4], [5, 4, 3]) 
------------------ 
([1, 0, 2, 3, 4], [4, 4, 3], 0, 1) 
([1, 0, 3, 2, 4], [4, 4, 2], 2, 3) 
([1, 0, 4, 2, 3], [4, 4, 1], 2, 4) 
reset------------------ 
([1, 0, 2, 3, 4], [4, 4, 3]) 
------------------ 
([1, 2, 0, 3, 4], [4, 3, 3], 1, 2) 
([1, 2, 3, 0, 4], [4, 3, 2], 2, 3) 
([1, 2, 4, 0, 3], [4, 3, 1], 2, 4)