在 Python 中按字典顺序查找字符串的第 n 次排列

pythonserver side programmingprogramming更新于 2025/10/10 21:32:17

假设我们有一个长度为 m 的字符串，并且该字符串仅包含小写字母，我们必须按字典顺序查找字符串的第 n 次排列。

因此，如果输入为 string = "pqr", n = 3，则输出将为 "qpr"因为所有排列都是 [pqr, prq, qpr, qrp, rpq, rqp]，所以它们是按排序顺序排列的。

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

MAX_CHAR := 26
MAX_FACT := 20
factorials := 大小为 MAX_FACT 的数组
factorials[0] := 1
对于范围从 1 到 MAX_FACT 的 i，执行
- factorials[i] := factorials[i - 1] * i
size := size of字符串
occurrence := 一个大小为 MAX_CHAR 的数组，用 0 填充
对于范围从 0 到 size 的 i，执行
- occurrence[(string[i]) 的 ASCII - ('a') 的 ASCII ] := appearance[(string[i]) 的 ASCII - ('a') 的 ASCII ] + 1
res := 一个大小为 MAX_CHAR 的数组
Sum := 0, k := 0
当 Sum 与 n 不同时，执行
- Sum := 0
- 对于范围中的 i 0 到 MAX_CHAR，执行
  - 如果发生[i]与0相同，则
    - 进行下一次迭代
  - occurrence[i] :=ogenesis[i] - 1
  - temp_sum := factorials[size - 1 - k]
  - 对于 j 在 0 到 MAX_CHAR 范围内，执行
    - temp_sum := temp_sum / factorials[occurrence[j]] (整数除法)
  - Sum := Sum + temp_sum
  - 如果 Sum >= n，然后
    - res[k] := 来自 ASCII 码的字符 (i + ASCII of('a'))
    - n := n - Sum - temp_sum
    - k := k + 1
    - 退出循环
  - 如果 Sum < n，则
    - occurrence[i] := appearance[i] + 1
i := MAX_CHAR-1
while k < size 且 i >= 0，则执行
- 如果发生[i]非零，则
  - res[k] := ASCII 码中的字符 (i + ASCII of('a'))
  - occurrence[i] := appearance[i] - 1
  - i := i + 1
  - k := k + 1
- i := i - 1
返回从索引 0 到 (k - 1) 的 res 生成的字符串

示例

让我们看看下面的实现以便更好地理解 −

MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * (MAX_FACT)
def get_nth_permute(string, n):
   factorials[0] = 1
   for i in range(1, MAX_FACT):
      factorials[i] = factorials[i - 1] * i
   size = len(string)
   occurrence = [0] * (MAX_CHAR)
   for i in range(0, size):
      occurrence[ord(string[i]) - ord('a')] += 1
   res = [None] * (MAX_CHAR)
   Sum = 0
   k = 0
   while Sum != n:
      Sum = 0
      for i in range(0, MAX_CHAR):
         if occurrence[i] == 0:
            continue
         occurrence[i] -= 1
         temp_sum = factorials[size - 1 - k]
         for j in range(0, MAX_CHAR):
            temp_sum = temp_sum // factorials[occurrence[j]]
         Sum += temp_sum
         if Sum >= n:
            res[k] = chr(i + ord('a'))
            n -= Sum - temp_sum
            k += 1
            break
         if Sum < n:
            occurrence[i] += 1
   i = MAX_CHAR-1
   while k < size and i >= 0:
      if occurrence[i]:
         res[k] = chr(i + ord('a'))
         occurrence[i] -= 1
         i += 1
         k += 1
      i -= 1
   return ''.join(res[:k])

n = 3
string = "pqr"
print(get_nth_permute(string, n))