程序在Python中查找满足给定条件的彩色顶点子集的数量
假设我们有一个数组颜色，代表一个常规n边形的颜色。在这里，这个n边形的每个顶点都被随机着色为给定数组中存在的n种不同颜色中的一种。我们必须找到多边形顶点的特殊子集的数量，以便这些子集满足这些条件-
子集的大小必须至少为2。
如果我们从多边形中移除存在于子集中的顶点（这些顶点的相邻边也将被移除），那么剩余的顶点和边将形成一些连续的路径。
这些路径都不应该包含两个相同颜色的顶点。
我们必须计算存在此类子集的数量。如果答案太大，则返回结果mod10^9+7。
因此，如果输入类似于颜色=[1,2,3,4]，那么输出将是11。
示例
让我们看看以下实现以获得更好的理解-
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