在Python中找到从n个自然数的排列中的魔术集合数量的程序

假设我们有一个数组A，其中包含n个自然数，并且一个数组A的排列P {p1，p2，…pn}。我们必须检查有多少个魔法集。排列被称为魔术集，如果满足以下几个规则−

如果我们有k，那么位置a[1]，a[2]，…a[k]的元素小于其相邻元素[P[a [i] – 1]> P [a [i]]
如果我们有l，则位置b[1]，b[2]，…b[l]的元素大于其相邻元素[P[b [i] – 1]

P [b [i] + 1]]

因此，如果输入为n = 4 k = 1 l = 1 k_vals = [2] l_vals = [3]，那么输出将为5，因为：N = 4，a [1] = 2，并且b [1] = 3。因此，五个排列是[2，1，4，3]，[3，2，4，1]，[4，2，3，1]，[3，1，4，2]，[4，1，3，2]。

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

p：= 10 ^ 9 + 7
F：=大小为n + 2的数组，并用0填充
对于每个k_vals中的a，执行以下操作，
- 如果F [a – 1]为1或F [a + 1]为1，则
  - 如果F [a – 1]为1或F [a + 输入]为1，则
  - p：= null
  - F [a]：= 1
对于l_vals中的每个b，执行以下操作，
- 如果F [b]为1或F [b – 1]为-1或F [b + 1]为-1，则
  - p：= null
- F [b]：= -1
如果p与null相同，则
- 返回0
否则，
- A：=大小为n + 1的数组，并用0填充
- B：=大小为n + 1的数组，并用0填充
- FF：=大小为n + 1的数组，并用null填充
- 对于i范围在1到n中，执行以下操作，
  - FF [i]：= F [i] – F [i – 1]
- A [1]：= 1
- 对于i范围在2到n中，执行以下操作，
  - 对于j范围在1到i中，执行以下操作，
  - 如果FF [i]> 0，则
    - B [j]：=（B [j – 1] + A [j – 1]）mod p
  - 否则，当FF [i] < 0时，
    - B [j]：=（B [j – 1] + A [i – 1] – A [j – 1]）mod p
  - 否则，
    - B [j]：=（B [j – 1] + A [i – 1]）mod p
  - 交换A和B
- 返回A [n]

示例

我们来看一下以下实现，以便更好地理解−

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