在Python中找出遇到给定条件的彩色顶点子集的数量

假设我们有一个数组colors，表示一个正则n边形的颜色。这里，这个n边形的每个顶点都随机着一种在给定数组中出现的n种不同颜色之一。我们必须找到特殊子集的多边形顶点数量，这些子集满足以下条件 –

子集的大小必须至少为两个。
如果我们从多边形中删除存在于子集中的顶点（那些顶点的相邻边也会被删除），则剩余的顶点和边形成一些连续路径。
这些路径中不应包含两个相同颜色的顶点。

我们必须统计出这样的子集的数量。如果答案太大，则返回结果mod 10 ^ 9 + 7。

因此，如果输入是colors = [1, 2, 3, 4]，则输出将为11。

为了解决这个问题，我们将遵循以下步骤 –

count ：一个所有值都为空列表的空映射。
n ：颜色的大小
对于范围为0到颜色大小-1的i，请执行以下操作
- 在count[colors[i]]的末尾插入i
answer ：0
对于2到n的范围，请执行以下操作
- answer ：answer + nCr(n,i)
对于count的所有键的列表中的每个i，请执行以下操作
- l0 ：count[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，则
    - answer ：answer – 1
返回answer

范例

让我们看以下实现以获得更好的理解 –

 from collections import defaultdict
 from math import factorial

 def nCr(n, i):
    if n == 1：
        返回1
    返回阶乘(n) //阶乘(i) //阶乘(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))