Python程式：求解可產生正確排列的數字之和

假設給定一個數字n，要求編寫所有可能的正整數（至n）排列。這些排列按字典序排序，編號從1到n!。其中一個排列被認為是特殊排列。在這個特殊排列中，某些值可能被遺忘，用0代替。我們需要找到可以等於原始排列的排列，然後將它們的編號相加，並將和作為程式的輸出。

例如，如果輸入的特殊排列 (input_arr) = [0, 2, 0]，n = 3，則輸出為7。可能有兩種可能的排列：[1, 2, 3]和[3, 2, 1]。這些排列的編號分別為2和5。因此，結果為5 + 2 = 7。

為了解決這個問題，我們將遵循以下步驟：

  • mod := 10^9 + 7
  • i2 := 2 ^ (modulo - 2) mod modulo
  • fact := 一個新的列表，包含值1
  • 對於 x 從 1 到 n+1，執行：
    • 在fact列表末尾插入 (fact的最後一個元素 * x) mod modulo
  • cnt := input_arr中0的出現次數
  • 如果 cnt 等於零，則：
    • res := 0
    • seen_list := 一個新的列表
    • 對於每個索引 i 從 1 開始和 input_arr 中的元素 x，執行：
      • tmp_val := 將x插入seenList保持排序順序的索引
      • res := res + fact[n-i] *(x - 1 - tmp_val)
      • res := res mod modulo
      • 將x插入seen_list在位置tmp_val
    • 返回 res + 1
  • 否則：
    • ik := (cnt ^ (modulo-2)) mod modulo
    • miss := 一個大小為n的新列表，初始化為True
    • 對於 input_arr 中的每個 x，執行：
      • 如果 x 不等於 0，則：
        • miss[x - 1] := False
    • miss_srtd := 一個新的列表
    • tmp := 0
    • 對於每個索引 i 從 1 開始和 miss 中的元素 x，執行：
      • 如果 x 不為零，則：
        • 在 miss_srtd 末尾插入 i
        • tmp := tmp + i
    • pre := 一個初始化為0的新列表
    • 對於 miss 中的每個 x，執行：
      • 在 pre 末尾插入 pre[-1] + x
    • cnt_cu := 0
    • s := tmp mod modulo * ik mod modulo
    • srtdw := 一個新的列表
    • res := 0
    • z := 0
    • 對於每個索引 i 從 1 開始和 input_arr 中的元素 x，執行：
      • 如果 x 不為零，則：
        • l := 將 x 插入 srtdw 保持排序順序的位置
        • tmp_val := 將 x 插入 srtdw 保持排序順序的位置
        • l := l + z * (將 x 插入 miss_srtd 保持排序順序的位置) mod modulo * ik mod modulo
        • p := x - 1 - l
        • p := p * fact[cnt]
        • p := p mod modulo
        • 將 x 插入 srtdw 在位置 tmp_val
        • cnt_cu := cnt_cu + cnt - pre[x]
      • 否則：
        • l := cnt_cu
        • l := l * ik
        • l := l + z * i2 mod modulo
        • p := s - 1 - l
        • p := p * fact[cnt]
        • p := p mod modulo
        • z := z + 1
        • res := res + p * fact[n-i] mod modulo
        • res := res mod modulo
    • 返回 (res + fact[cnt]) mod modulo

示例

讓我們看下面的實現來更好地理解：

import bisect

def solve(input_arr, n):

   modulo = 10 ** 9 + 7
   i2 = pow(2, modulo-2, modulo)
   fact = [1]
   for x in range(1, n+1):
      fact.append(fact[-1] * x % modulo)

   cnt = input_arr.count(0)

   if not cnt:
      res = 0
      seen_list = []
      for i, x in enumerate(input_arr, 1):
         tmp_val = bisect.bisect(seen_list, x)
         res += fact[n-i] * (x - 1 - tmp_val)
         res %= modulo
         seen_list.insert(tmp_val, x)
      return res + 1
   else:
      ik = pow(cnt, modulo-2, modulo)
      miss = [True] * n
      for x in input_arr:
         if x != 0: miss[x-1] = False
      miss_srtd = []
      tmp = 0
      for i, x in enumerate(miss, 1):
         if x:
            miss_srtd.append(i)
            tmp += i
      pre = [0]
      for x in miss:
         pre.append(pre[-1] + x)
      cnt_cu = 0
      s = tmp % modulo * ik % modulo
      srtdw = []
      res = z = 0
      for i, x in enumerate(input_arr, 1):
         if x:
            l = tmp_val = bisect.bisect(srtdw, x)
            l += z * bisect.bisect(miss_srtd, x) % modulo * ik % modulo
            p = x - 1 - l
            p *= fact[cnt]
            p %= modulo
            srtdw.insert(tmp_val, x)
            cnt_cu += cnt - pre[x]
         else:
            l = cnt_cu
            l *= ik
            l += z * i2 % modulo
            p = s - 1 - l
            p *= fact[cnt]
            p %= modulo
            z += 1
         res += p * fact[n-i] % modulo
         res %= modulo
      return (res + fact[cnt])%modulo

print(solve([0, 2, 0], 3))

輸入

[0, 2, 0], 3

輸出

7

更新於：2021年10月11日

瀏覽量：135

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告