निरंतर राशि के साथ सरणी संयोजनों के माध्यम से पुनरावृत्त कैसे करें?

Question

मेरे पास एक सरणी है और इसकी लंबाई X है। सरणी के प्रत्येक तत्व में 1 .. L है। मैं सभी सरणी संयोजनों के माध्यम से कुशलता से पुन: प्रयास करना चाहता हूं जिसमें L है।

के लिए सही समाधान: एल = 4 और एक्स = 2

1 3 
3 1 
2 2 

के लिए सही समाधान: एल = 5 और एक्स = 3

1 1 3 
1 3 1 
3 1 1 
1 2 2 
2 1 2 
2 2 1 

अनुभवहीन कार्यान्वयन है (कोई आश्चर्य नहीं) बहुत धीमी गति से मेरी समस्या के लिए (एक्स मेरे मामले में 8 तक है और एल 128 तक है)।

क्या कोई मुझे बता सकता है कि इस समस्या को कैसे कहा जाता है या समस्या के लिए तेज़ एल्गोरिदम कहां मिल सकता है?

धन्यवाद!

Answer 1

अगर मैं सही ढंग से समझ, आप दो नंबर 1 ≤ एक्स दिया जाता है ≤ एल और आप एल को लंबाई एक्स कि राशि का धनात्मक पूर्णांक के सभी दृश्यों उत्पन्न करना चाहते हैं।

(नोट: यह integer partition problem के समान है, लेकिन ऐसा नहीं है, क्योंकि आप 1,2,2 से 2,2,2 से अलग अनुक्रम मानते हैं, जबकि पूर्णांक विभाजन समस्या में हम ऑर्डर को अनदेखा करते हैं, ताकि ये वही विभाजन माना जाता है)

दृश्यों कि आप की combinations एक्स से संबद्ध देख रहे हैं -। एल में से 1 आइटम - 1. के लिए, यदि हम संख्या डाल 1 एल - 1 क्रम में, और एक्स - उनमें से 1 चुनें, फिर चुने गए के बीच अंतराल की लंबाई संख्याएं सकारात्मक पूर्णांक हैं जो एल पर योग करती हैं।

उदाहरण के लिए, मान लीजिए कि एल 16 और एक्स है 5. फिर 1 से 15 समावेशी करने के लिए 4 नंबर का चयन है:

शुरुआत में 0 जोड़ें और 16 अंत में , और अंतराल हैं:

और 3 + 4 + 1 + 6 + 2 = 16 के रूप में की आवश्यकता है। एल में से 1 आइटम - -

तो एक्स की generate the combinations 1, और हर एक के लिए, अंतराल का पता लगाकर एक विभाजन करने के लिए परिवर्तित। उदाहरण के लिए, पायथन में आप लिख सकते हैं:

from itertools import combinations 

def partitions(n, t): 
    """ 
    Generate the sequences of `n` positive integers that sum to `t`. 
    """ 
    assert(1 <= n <= t) 
    def intervals(c): 
     last = 0 
     for i in c: 
      yield i - last 
      last = i 
     yield t - last 
    for c in combinations(range(1, t), n - 1): 
     yield tuple(intervals(c)) 

>>> list(partitions(2, 4)) 
[(1, 3), (2, 2), (3, 1)] 
>>> list(partitions(3, 5)) 
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)] 

हैं (एल - 1)!/(एक्स - 1)! (एल - एक्स)!एक्स के संयोजन - एल - 1 में से 1 आइटम, इसलिए इस एल्गोरिदम (और इसके आउटपुट का आकार) का रनटाइम एल में घातीय है। हालांकि, अगर आप आउटपुट की गणना नहीं करते हैं, तो इसे केवल ओ (एल) स्थान की आवश्यकता है।

एल के साथ

= 128 और एक्स = 8, ८९३५६४१५७७५ विभाजन देखते हैं, तो यह उन सब को उत्पादन के लिए कुछ समय ले जाएगा!

(हो सकता है कि अगर तुम तुम क्यों इन विभाजनों की गणना कर रहे हैं, हम वास्तव में उन सब का उत्पादन करने के बिना अपने आवश्यकताओं को पूरा करने के किसी तरह का सुझाव देने में सक्षम हो सकता समझाने।)