कार्यक्रम रंगीन कोने के सबसेट की संख्या का पता लगाता है जो पायथन में दी गई शर्तों को पूरा करता है

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

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

हमें ऐसे उपसमुच्चयों की संख्या गिनना है जो उपस्थित हैं। अगर उत्तर बहुत बड़ा है, तो परिणाम मोड 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट रंगों की तरह है =[1,2,3,4], तो आउटपुट 11 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

उदाहरण

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

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]