Python程式：查詢大小為k的1到n範圍內第k個字典序序列

假設我們有兩個值n和k。現在考慮一個從1到n的數字列表[1, 2, ..., n]，並生成此列表的每個排列的字典序序列。例如，如果n = 4，我們有[1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321]。我們必須找到此排列序列的第k個值作為字串。

因此，如果輸入類似於n = 4 k = 5，則輸出將為“1432”。

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

  • 定義一個函式factors()。它將接收num作為輸入。

  • quo := num

  • res := 一個雙端佇列，並在開頭插入0。

  • i := 2

  • 當quo不為空時，執行以下操作：

    • quo := (quo / i)的商，rem := quo mod i

    • 在res的左側插入rem

    • i := i + 1

  • 返回res

  • 從主方法執行以下操作：

  • numbers := 一個包含從1到n值的列表

  • res := 空字串

  • k_fact := factors(k)

  • 當k_fact的大小小於numbers的大小。

    • res := res連線numbers的第一個元素作為字串，然後刪除numbers的第一個元素

  • 對於k_fact中的每個索引，執行以下操作：

    • number := numbers的第index個元素，然後刪除該元素

    • res := res連線number

  • 返回res

讓我們看看以下實現，以便更好地理解：

示例

 線上演示

from collections import deque
def factors(num):
   quo = num
   res = deque([0])
   i = 2
   while quo:
      quo, rem = divmod(quo, i)
      res.appendleft(rem)
      i += 1
   return res
class Solution:
   def solve(self, n, k):
      numbers = [num for num in range(1, n + 1)]
      res = ""
      k_fact = factors(k)
      while len(k_fact) < len(numbers):
         res += str(numbers.pop(0))
      for index in k_fact:
         number = numbers.pop(index)
         res += str(number)
      return res
ob = Solution()
n = 4
k = 5
print(ob.solve(n, k))

輸入

4, 5

輸出

1432

更新於: 2020年12月26日

154 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.