Chương trình tìm số lượng tập con của các đỉnh đầy màu sắc đáp ứng các điều kiện nhất định trong Python

Giả sử chúng ta có một mảng màu, đại diện cho các màu cho một n-gon thông thường. Ở đây mỗi đỉnh của n-gon này được tô màu ngẫu nhiên với một trong n màu khác nhau có mặt trong mảng đã cho. Chúng ta phải tìm số lượng các tập con đặc biệt của các đỉnh đa giác, sao cho các tập con này đáp ứng các điều kiện này -

• Kích thước của tập hợp con phải có ít nhất hai.
• Nếu chúng ta loại bỏ các đỉnh có trong tập hợp con, khỏi đa giác (các cạnh liền kề của các đỉnh đó cũng sẽ bị xóa), thì các đỉnh và cạnh còn lại sẽ tạo thành một số đường đi liên tục.
• Không có đường dẫn nào trong số đó phải chứa hai đỉnh cùng màu.

Chúng ta phải đếm số lượng các tập hợp con như vậy có mặt. Nếu câu trả lời quá lớn, thì trả về kết quả mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như color =[1,2,3,4], thì đầu ra sẽ là 11.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• count:=một bản đồ trống trong đó tất cả các giá trị sẽ là một danh sách trống.
• n:=kích thước của màu sắc
• đối với tôi trong phạm vi từ 0 đến kích thước của các màu - 1, thực hiện
  • chèn i vào cuối số [màu [i]]
• câu trả lời:=0
• đối với tôi trong phạm vi từ 2 đến n, thực hiện
  • answer:=answer + nCr (n, i)
• đối với mỗi i trong danh sách tất cả các khóa đếm, hãy thực hiện
  • l0:=count [i]
  • n0:=kích thước của l0
  • nếu n0> 1, thì
    • đối với tôi trong phạm vi từ 0 đến n0-2, thực hiện
      • đối với j trong phạm vi i + 1 đến n0 - 1, thực hiện
        • d1:=l0 [j] -l0 [i]
        • d2:=l0 [i] -l0 [j] + n
        • nếu d1 <=n-3 hoặc d2 <=n-3, thì
          • answer:=answer - 1
• trả lời câu trả lời

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[1,2,3,4]

Đầu ra

11