পাইথনে 1 থেকে n পর্যন্ত সংখ্যার kth লেক্সিকোগ্রাফিক পারমুটেশন বের করা

ধরুন, n এবং k দুটি মান দেওয়া আছে। ১ থেকে n পর্যন্ত সংখ্যার সব পারমুটেশন লেক্সিকোগ্রাফিক অর্ডারে সাজানোর পর k-তম পারমুটেশনটি স্ট্রিং হিসেবে রিটার্ন করতে হবে।

উদাহরণস্বরূপ, n = 4, k = 5 হলে পারমুটেশনগুলো: 1234, 1243, 1324, 1342, 1423, 1432, ...। ৫তমটি হলো "1432"।

সমাধানের ধাপসমূহ (ফ্যাক্টোরিয়াল নম্বর সিস্টেম)

1. factors(num) ফাংশন ডিফাইন করুন যা num-কে ফ্যাক্টোরিয়াল বেসে রূপান্তর করে (ফ্যাক্টোরিয়াল রিপ্রেজেন্টেশন)।

2. numbers := [1, 2, ..., n]

3. k_fact := factors(k)

4. যতক্ষণ len(k_fact) < len(numbers), ততক্ষণ numbers-এর প্রথম উপাদানটি রেজাল্টে যোগ করুন এবং মুছে দিন।

5. প্রতিটি index ∈ k_fact এর জন্য:

   • numbers[index] উপাদানটি রেজাল্টে যোগ করুন এবং মুছে দিন।

6. ফাইনাল স্ট্রিং রিটার্ন করুন।

পাইথন কোড উদাহরণ

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