Giả sử chúng ta có hai giá trị n và k. Bây giờ hãy xem xét một danh sách các số trong phạm vi từ 1 đến n [1, 2, ..., n] và tạo ra mọi hoán vị của danh sách này theo trình tự từ điển học. Ví dụ:nếu n =4 chúng ta có [1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321]. Chúng ta phải tìm giá trị thứ k của chuỗi hoán vị này dưới dạng một chuỗi.
Vì vậy, nếu đầu vào là n =4 k =5, thì đầu ra sẽ là "1432"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một yếu tố hàm (). Điều này sẽ mất số
-
quo:=num
-
res:=một hàng đợi kết thúc kép và chèn 0 ở đầu
-
i:=2
-
trong khi quo không trống, thực hiện
-
quo:=quo của (quo / i), rem:=quo mod i
-
chèn rem ở bên trái của res
-
i:=i + 1
-
-
trả lại res
-
Từ phương thức chính, hãy làm như sau -
-
number:=một danh sách có các giá trị từ 1 đến n
-
res:=chuỗi trống
-
k_fact:=factor (k)
-
trong khi kích thước của k_fact
-
res:=res nối phần tử đầu tiên của số dưới dạng chuỗi, sau đó xóa phần tử đầu tiên của số
-
-
đối với mỗi chỉ mục trong k_fact, thực hiện
-
number:=phần tử thứ-chỉ số của các số, sau đó xóa phần tử đó
-
res:=res nối số
-
-
trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
4, 5
Đầu ra
1432