数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python 中字符串的第 n 个字典序排列
假设我们有一个长度为 m 的字符串，该字符串只包含小写字母，我们需要找到该字符串的字典序第 n 个排列。
例如，如果输入字符串为 "pqr"，n = 3，则输出为 "qpr"，因为所有排列为 [pqr, prq, qpr, qrp, rpq, rqp]，它们按排序顺序排列。
为了解决这个问题，我们将遵循以下步骤：
MAX_CHAR := 26
MAX_FACT := 20
factorials := 一个大小为 MAX_FACT 的数组
factorials[0] := 1
对于 i 从 1 到 MAX_FACT，执行：
factorials[i] := factorials[i - 1] * i
size := 字符串的大小
occurrence := 一个大小为 MAX_CHAR 的数组，填充为 0
对于 i 从 0 到 size，执行：
occurrence[ASCII(string[i]) - ASCII('a')] := occurrence[ASCII(string[i]) - ASCII('a')] + 1
res := 一个大小为 MAX_CHAR 的数组
Sum := 0, k := 0
当 Sum 不等于 n 时，执行：
Sum := 0
对于 i 从 0 到 MAX_CHAR，执行：
如果 occurrence[i] 等于 0，则
跳过本次迭代
occurrence[i] := occurrence[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('a')) 的字符
n := n - Sum - temp_sum
k := k + 1
跳出循环
如果 Sum < n，则
occurrence[i] := occurrence[i] + 1
i := MAX_CHAR - 1
当 k < size 且 i >= 0 时，执行：
如果 occurrence[i] 不为零，则
res[k] := ASCII 码为 (i + ASCII('a')) 的字符
occurrence[i] := occurrence[i] - 1
i := i + 1
k := k + 1
i := i - 1
返回从 res 的索引 0 到 (k - 1) 组成的字符串
示例
让我们来看下面的实现，以便更好地理解：
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))输入
"pqr"
输出
qpr
174 次浏览
