在 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 = 4 k = 1 l = 1 k_vals = [2] l_vals = [3]，那么输出将为 5，因为：N = 4, a[1] = 2 and b[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