โปรแกรมค้นหาจำนวนชุดย่อยของจุดยอดที่มีสีสันที่ตรงตามเงื่อนไขที่กำหนดในPython

สมมติว่าเรามีสีอาร์เรย์ แทนสีสำหรับ n-gon ปกติหนึ่งอัน จุดยอดแต่ละจุดของ n-gon นี้จะถูกสุ่มสีด้วยหนึ่งใน n สีที่แตกต่างกันในอาร์เรย์ที่กำหนด เราต้องหาจำนวนชุดย่อยพิเศษของจุดยอดหลายเหลี่ยมเพื่อให้ชุดย่อยเหล่านี้ตรงตามเงื่อนไขเหล่านี้ -

• ขนาดของเซตย่อยต้องมีอย่างน้อยสองขนาด
• หากเราลบจุดยอดซึ่งมีอยู่ในเซตย่อย ออกจากรูปหลายเหลี่ยม (ขอบที่อยู่ติดกันของจุดยอดเหล่านั้นจะถูกลบออกด้วย) จากนั้นจุดยอดและขอบที่เหลือจะสร้างเส้นทางที่ต่อเนื่องกัน
• เส้นทางเหล่านั้นไม่ควรมีจุดยอดสองจุดที่มีสีเดียวกัน

เราต้องนับจำนวนชุดย่อยดังกล่าวที่มีอยู่ หากคำตอบมีขนาดใหญ่เกินไป ให้คืนค่า mod ผลลัพธ์ 10^9 + 7

ดังนั้น หากอินพุตเป็นเหมือนสี =[1,2,3,4] ผลลัพธ์จะเป็น 11

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จำนวน :=แผนที่ว่างซึ่งค่าทั้งหมดจะเป็นรายการที่ว่างเปล่า
• n :=ขนาดของสี
• สำหรับฉันในช่วง 0 ถึงขนาดของสี - 1 ทำ
  • แทรก i ที่ท้ายการนับ[colors[i]]
• คำตอบ :=0
• สำหรับฉันในช่วง 2 ถึง n ทำ
  • answer :=answer + nCr(n, i)
• สำหรับแต่ละ i ในรายการคีย์ทั้งหมดของการนับ ทำ
  • l0 :=นับ[i]
  • n0 :=ขนาดของ l0
  • ถ้า n0> 1 แล้ว
    • สำหรับฉันในช่วง 0 ถึง n0-2 ทำ
      • สำหรับ j ในช่วง i+1 ถึง n0 - 1 ทำ
        • d1 :=l0[j] -l0[i]
        • d2 :=l0[i] -l0[j] + n
        • ถ้า d1 <=n-3 หรือ d2<=n-3 แล้ว
          • answer :=ตอบ - 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]

ผลลัพธ์

11