Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में दी गई शर्तों को पूरा करने वाले रंगीन शीर्षों के उपसमुच्चयों की संख्या खोजने का प्रोग्राम


मान लीजिए हमारे पास एक ऐरे colors है, जो एक नियमित n-gon के लिए रंगों का प्रतिनिधित्व करता है। यहां इस n-gon के प्रत्येक शीर्ष को दिए गए ऐरे में मौजूद n अलग-अलग रंगों में से एक के साथ रैंडमली रंगा गया था। हमें बहुभुज शीर्षों के विशेष उपसमुच्चयों की संख्या ढूंढनी है, जैसे कि ये उपसमुच्चय इन शर्तों को पूरा करते हैं:

  • उपसमुच्चय का आकार कम से कम दो होना चाहिए।
  • यदि हम उपसमुच्चय में मौजूद शीर्षों को बहुभुज से हटा दें (उन शीर्षों के आसन्न किनारे भी हट जाएंगे), तो शेष शीर्ष और किनारे कुछ सतत पथ बनाते हैं।
  • उन पथों में से कोई भी दो शीर्ष नहीं होने चाहिए जिनका रंग समान हो।

हमें गिनना है कि ऐसे कितने उपसमुच्चय मौजूद हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम mod 10^9 + 7 वापस करें।

तो, यदि इनपुट colors = [1,2,3,4] है, तो आउटपुट 11 होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • count := एक खाली मैप जहां सभी मान खाली सूची होंगे।
  • n := colors का आकार
  • i के लिए range 0 से colors के आकार - 1 तक, करें
    • i को count[colors[i]] के अंत में डालें
  • answer := 0
  • i के लिए range 2 से n तक, करें
    • answer := answer + nCr(n, i)
  • count की सभी कुंजियों की सूची में प्रत्येक i के लिए, करें
    • l0 := count[i]
    • n0 := l0 का आकार
    • यदि n0 > 1, तो
      • i के लिए range 0 से n0-2 तक, करें
        • j के लिए range i+1 से n0 - 1 तक, करें
          • d1 := l0[j] -l0[i]
          • d2 := l0[i] -l0[j] + n
          • यदि d1 <= n-3 या d2 <= n-3, तो
            • answer := answer - 1
  • answer वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

from collections import defaultdict from math import factorial def nCr(n, i): if n==1: return 1 return factorial(n)//factorial(i)//factorial(n-i) def solve(colors): count = defaultdict(list) n = len(colors) for i in range(len(colors)): count[colors[i]].append(i) answer = 0 for i in range(2, n+1): answer += nCr(n, i) for i in count.keys(): l0 = count[i] n0 = len(l0) if n0 > 1: for i in range(n0-1): for j in range(i+1, n0): d1 = l0[j] -l0[i] d2 = l0[i] -l0[j] + n if d1 <= n-3 or d2 <= n-3: answer -=1 return answer colors = [1,2,3,4] print(solve(colors))

इनपुट

[1,2,3,4] 

आउटपुट

11

  1. Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें? Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें?

    डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं। एल्गोरिदम सभी नोड्स का सेट बनाएं (0 से n-1)। सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं। सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)। यही मिनिमम वर्टेक्स सेट है। उद

  1. पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम

    मान लीजिए हमारे पास (u, v) के रूप में एज की सूची है जो एक ट्री दर्शाती है। प्रत्येक एज के लिए हमें उन अद्वितीय पथों की कुल संख्या ज्ञात करनी है जिनमें वह एज शामिल है, उसी क्रम में जैसे इनपुट में दिया गया है। उदाहरण के लिए, यदि इनपुट है edges = [[0, 1],[0, 2],[1, 3],[1, 4]], तो आउटपुट [6, 4, 4, 4] ह

  1. पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास रंगों (R, G, B) की एक लिस्ट है। अब यदि दो अलग-अलग रंग अगल-बगल हैं तो वे तीसरे रंग के एकल रंग आइटम में बदल सकते हैं। हमें किसी भी संभावित परिवर्तन अनुक्रम के बाद शेष सबसे छोटी संख्या ढूंढनी है।उदाहरण के लिए, यदि इनपुट colors = [G, R, G, B, R] है, तो आउटपुट 1 होगा क्योंकि यह नीचे द