在 Python 中从前 n 个自然数的排列中查找魔法集数的程序
假设我们有一个包含前n个自然数的数组A，以及数组A的一个排列P{p1,p2,...pn}。我们必须检查有多少个魔法集。如果满足以下几条规则，则排列被称为魔术集-
如果我们有k，那么位置a[1],a[2],...a[k]中的元素小于它们的相邻元素[P[a[i]-1]>P[a[i]]<P[a[i]+1]]
如果我们有l，那么位置b[1],b[2],...b[l]中的元素大于它们的相邻元素[P[b[i]-1]<P[b[i]]>P[b[i]+1]]
因此，如果输入类似于n=4k=1l=1k_vals=[2]l_vals=[3]，那么输出将为5，因为：N=4,a[1]=2andb[1]=3.所以五个排列是[2,1,4,3],[3,2,4,1],[4,2,3,1],[3,1,4,2],[4,1,3,2]。
示例
让我们看看以下实现以获得更好的理解-
def solve(n, k, l, k_vals, l_vals):
p = 10**9+7
F = [0] * (n + 2)
for a in k_vals:
if F[a - 1] == 1 or F[a + 1] == 1:
p = None
F[a] = 1
for b in l_vals:
if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
p = None
F[b] = -1
if p == None:
return 0
else:
A = [0] * (n + 1)
B = [0] * (n + 1)
FF = [None] * (n + 1)
for i in range(1, n + 1):
FF[i] = F[i] - F[i - 1]
A[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
if FF[i] > 0:
B[j] = (B[j - 1] + A[j - 1]) % p
elif FF[i] < 0:
B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
else:
B[j] = (B[j - 1] + A[i - 1]) % p
A, B = B, A
return A[n]
n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))输入
4, 1, 1, [2], [3]
输入
5