สมมติว่าเรามีสองค่า 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]. เราต้องหาค่า kth ของลำดับการเรียงสับเปลี่ยนนี้เป็นสตริง
ดังนั้น หากอินพุตเป็น n =4 k =5 เอาต์พุตจะเป็น "1432"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน factor() นี่จะใช้เวลา num
-
quo :=num
-
res :=ดับเบิ้ลคิวและใส่ 0 ที่จุดเริ่มต้น
-
ผม :=2
-
ในขณะที่ยังไม่ว่างให้ทำ
-
quo :=ผลหารของ (quo / i), rem :=quo mod i
-
ใส่ rem ที่ด้านซ้ายของ res
-
ผม :=ผม + 1
-
-
ผลตอบแทน
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ตัวเลข :=รายการที่มีค่า 1 ถึง n
-
res :=สตริงว่าง
-
k_fact :=ปัจจัย (k)
-
ในขณะที่ขนาดของ k_fact <ขนาดของตัวเลข ทำ
-
res :=res เชื่อมองค์ประกอบแรกของตัวเลขเป็นสตริง จากนั้นลบองค์ประกอบแรกของตัวเลข
-
-
สำหรับแต่ละดัชนีใน k_fact ทำ
-
number :=องค์ประกอบ index−th ของตัวเลข จากนั้นลบองค์ประกอบนั้นออก
-
res :=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
