資料結構
網路
關係資料庫管理系統 (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 次瀏覽
