क्रमपरिवर्तन, लेकिन कुछ संख्याओं के साथ

Question

ठीक है, मेरे पास ब्राउज़ किया गया है और मैं इस समस्या के लिए या तो सी या पायथन समाधान ढूंढ रहा हूं। मैं अजगर पसंद करूंगा ... हालांकि यह मेरी कमजोर भाषा है (2 बहुत कमजोर भाषाओं में)।

संख्याओं के एक सेट, इस तरह के रूप में 0 0 1 7 0 0 3 0 0 4

1. सेट के सभी क्रमपरिवर्तन का पता लगाएं।
2. संख्या> 0 उस क्रम में रहना चाहिए (पॉजिशन!)
3. संख्याओं के बीच 0 होना चाहिए, हालांकि सेट की शुरुआत और अंत में 0 की आवश्यकता नहीं है। जब तक संख्या 0 के बीच कम से कम 0 0 है।

तो सबसे पहले, मैंने केवल सभी संभावित क्रमपरिवर्तनों को खोजने और फिर प्रत्येक क्रमपरिवर्तन के लिए चाफ को हटाने (अगर एन> 0,! एन + 1> 0) की जांच की और फिर पहली संख्या> 0 == 1 , दूसरा #> 0 == 7 इत्यादि।

मैंने तब रुक दिया और सोचा कि यह दांव था, कहें कि 12 संख्याएं थीं, जो 12 देगी! क्रमपरिवर्तन। यह 500,000,000 क्रमिक क्रम के क्रम में मुझे चाफ से छुटकारा पाने के लिए फिर से दौड़ना होगा।

कहें कि मेरे पास इन नंबर सेटों के 40-50 सेट हैं, जो कि समय के लिए उचित है।

क्या कोई और तार्किक तरीका है? मैंने सोचा कि किसी भी तरह से उन नियमों को ध्यान में रखते हुए पाइथन करते हैं (यदि एन> 0, एन + 1 मस्त == 0) और (एन = पहला नंबर, एन 2 = दूसरा आदि)

का एक उदाहरण एक छोटा समूह (नहीं सभी क्रमपरिवर्तन है, लेकिन विचार देता है) होगा:

1,2,3,0,0,0,0,0

1. 1,0,2,0, 3,0,0,0
2. 0,1,0,2,0,3,0,0
3. 0,0,1,0,2,0,3,0
4. 0,0,1,0,0,2,0,3
5. 0,1,0,0,2,0,3,0

आदि आदि तो 1, 2,3 क्रम में है लेकिन "0" बस के बारे में स्थानांतरित कर रहे हैं?

धन्यवाद!

Answer 1

असल में आप उन संयोजनों की संख्या को कम करना चाहते हैं जिन्हें आप अपने आविष्कारों के अनुसार चीजों को समूहीकृत करके गणना करना चाहते हैं। के बाद से गैर शून्य संख्या एक निश्चित क्रम में होना चाहिए की उस के साथ शुरू करते हैं:

1 2 3 

के बाद से वहाँ होना चाहिए 0 उन दोनों के बीच उन्हें

1 0 2 0 3 

अब क्या आप के साथ छोड़ दिया जाता है में जोड़ने के तीन 0 की है जगह बनाने के लिए और आपको यह समझने की जरूरत है कि कितने संयोजन अलग-अलग अनुक्रम देते हैं। स्पष्ट रूप से इस उदाहरण से आपके पास संभावित स्थितियां हैं: 1 से पहले, 1 और 2 के बीच, 2 और 3 के बीच और 3 के बाद। आपके पास 4 पद हैं जिसमें यह तय करने के लिए कि शेष तीन 0 को कैसे विभाजित किया जाए। यह एक combination problem with repetition है, जिसके लिए यहां समाधान (3 + 4 - 1) Choose 3 (जो 20 है)।

उम्मीद है कि जिस तरह से है कि मैं इस उदाहरण समस्या माध्यम से चला गया पर्याप्त आप मनमाने ढंग से दृश्यों को यह सामान्यीकरण करने के लिए है, इसलिए मुझे लगता है कि छोड़ देंगे पाठक के लिए एक व्यायाम के रूप है।

Answer 2

def find_permutations(l): 
    n = [e for e in l if e] # Strip zeros. 
    # Interspace non-zeros with zeros. 
    m = [j for i in n for j in (i,0)][:-1] 
    def fill(m): 
     if len(m) == len(l): 
      yield tuple(m) 
     else: 
      # Recursively fill with zeros. 
      for i in range(len(m)+1): 
       for o in fill(m[:i] + [0] + m[i:]): 
        yield tuple(o) 
    return sorted(set(fill(m))) 

मुझे लगता है कि इसे कवर करना चाहिए। तो उदाहरण के लिए (पायथन 3 में), आप कर सकते हैं:

>>> [print(p) for p in find_permutations([1,2,3,0,0,0,0,0])] 
(0, 0, 0, 1, 0, 2, 0, 3) 
(0, 0, 1, 0, 0, 2, 0, 3) 
(0, 0, 1, 0, 2, 0, 0, 3) 
(0, 0, 1, 0, 2, 0, 3, 0) 
(0, 1, 0, 0, 0, 2, 0, 3) 
(0, 1, 0, 0, 2, 0, 0, 3) 
(0, 1, 0, 0, 2, 0, 3, 0) 
(0, 1, 0, 2, 0, 0, 0, 3) 
(0, 1, 0, 2, 0, 0, 3, 0) 
(0, 1, 0, 2, 0, 3, 0, 0) 
(1, 0, 0, 0, 0, 2, 0, 3) 
(1, 0, 0, 0, 2, 0, 0, 3) 
(1, 0, 0, 0, 2, 0, 3, 0) 
(1, 0, 0, 2, 0, 0, 0, 3) 
(1, 0, 0, 2, 0, 0, 3, 0) 
(1, 0, 0, 2, 0, 3, 0, 0) 
(1, 0, 2, 0, 0, 0, 0, 3) 
(1, 0, 2, 0, 0, 0, 3, 0) 
(1, 0, 2, 0, 0, 3, 0, 0) 
(1, 0, 2, 0, 3, 0, 0, 0) 

क्या यह आपके मन में समान था?

संपादित करें: मूल रूप से fill नामक फ़ंक्शन को प्रत्येक सूची के बीच शून्य दर्ज किया जाता है, और रिकर्स होता है। जब भी पर्याप्त संख्या fill समारोह में दर्ज किया जाता संख्या का एक टपल दिया जाता है (रिकर्सिवली उत्पन्न नंबर की सूची लंबाई मूल इनपुट की सूची की लंबाई के बराबर होती है)।

लौटने पर टुपल्स में कनवर्ट करने का एकमात्र कारण यह है कि find_permutations फ़ंक्शन की अंतिम पंक्ति पर दिखाई देने के प्रकार को सेट में उपयोग करने के लिए हैशबल होना चाहिए। sorted अच्छीता के लिए है।