Python程序：查找从1到n的大小为k的字典序第k个序列

假设我们有两个值n和k。现在考虑一组数字[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
while quo不为空，执行以下操作
- quo:=quo / i的商，rem:=quo模i
- 在res左侧插入rem
- i:=i + 1
返回res
从main方法执行以下操作
numbers：值为1到n的列表
res：空字符串
k_fact：factors(k)
while k_fact的大小小于numbers的大小，执行以下操作
- res：将numbers的第一个元素作为字符串连接到res上，然后删除numbers的第一个元素
对于k_fact中的每个索引，执行以下操作
- number：numbers的第index-1个元素，然后删除该元素
- res：将number连接到res上
返回res

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

更多Python相关文章，请阅读：Python 教程

示例

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 - 1)
            res += str(number)
        return res
ob = Solution()
n = 4
k = 5
print(ob.solve(n, k))