在Python中按字符串的字母顺序查找第n个排列
假设我们有一个长度为m的字符串，并且该字符串仅包含小写字母，我们必须按字典顺序查找字符串的第n个置换。
因此，如果输入类似于string=“pqr”，n=3，则输出将为“qpr”，因为所有排列均为[pqr，prq，qpr，qrp，rpq，rqp]，它们的排列顺序相同。
为了解决这个问题，我们将遵循以下步骤-
MAX_CHAR：=26
MAX_FACT：=20
阶乘：=大小为MAX_FACT的数组
阶乘[0]：=1
对于范围1至MAX_FACT的i，执行
阶乘[i]：=阶乘[i-1]*i
大小：=字符串大小
出现：=大小为MAX_CHAR的数组，用0填充
对于介于0到大小范围内的i，执行
事件[（string[i]）的ASCII-（'a'）的ASCII]：=事件[（字符串[i]）的ASCII-（'a'）的ASCII]+1
res：=大小为MAX_CHAR的数组
和：=0，k：=0
虽然Sum与n不同，但是
如果出现[i]与0相同，则
出现[i]：=出现[i]-1
temp_sum：=阶乘[大小-1-k]
对于范围0到MAX_CHAR的j，执行
总和：=总和+temp_sum
如果Sum>=n，则
如果Sum<n，则
进行下一次迭代
temp_sum：=temp_sum/factorials[occurrence[j]]（整数除法）
res[k]：=来自ASCII码的字符（i+（'a'）的ASCII）
n：=n-总和-temp_sum
k：=k+1
从循环中出来
发生[i]：=发生[i]+1
总和：=0
对于0到MAX_CHAR范围内的i，执行
我：=MAX_CHAR-1
当k<大小且i>=0时，
res[k]：=来自ASCII码的字符（i+（'a'）的ASCII）
出现[i]：=出现[i]-1
我：=我+1
k：=k+1
如果出现[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