ধরা যাক একটি স্ট্রিং আছে যার দৈর্ঘ্য m এবং এতে শুধু ছোট হাতের অক্ষর রয়েছে। আমাদের এই স্ট্রিং-এর n-th পারমুটেশন লেক্সিকোগ্রাফিক্যাল অর্ডারে বের করতে হবে।
যেমন, ইনপুট string = "pqr", n = 3 হলে আউটপুট হবে "qpr" কারণ সকল পারমুটেশন সর্টেড অর্ডারে: [pqr, prq, qpr, qrp, rpq, rqp]।
সমাধানের ধাপসমূহ
- MAX_CHAR := 26, MAX_FACT := 20
- factorials অ্যারে তৈরি করুন এবং প্রीकম্পিউট করুন
- প্রতিটি ক্যারেক্টার এর ফ্রিকোয়েন্সি গণনা করুন
- ফ্যাক্টোরিয়াল এবং ফ্রিকোয়েন্সি ব্যবহার করে n-th পারমুটেশন কনস্ট্রাক্ট করুন
উদাহরণ
MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * (MAX_FACT)
def get_nth_permute(string, n):
factorials[0] = 1
for i in range(1, MAX_FACT):
factorials[i] = factorials[i - 1] * i
size = len(string)
occurrence = [0] * (MAX_CHAR)
for i in range(size):
occurrence[ord(string[i]) - ord('a')] += 1
res = [None] * (MAX_CHAR)
Sum = 0
k = 0
while Sum != n:
Sum = 0
for i in range(MAX_CHAR):
if occurrence[i] == 0:
continue
occurrence[i] -= 1
temp_sum = factorials[size - 1 - k]
for j in range(MAX_CHAR):
temp_sum //= factorials[occurrence[j]]
Sum += temp_sum
if Sum >= n:
res[k] = chr(i + ord('a'))
n -= Sum - temp_sum
k += 1
break
if Sum < n:
occurrence[i] += 1
i = MAX_CHAR - 1
while k < size and i >= 0:
if occurrence[i]:
res[k] = chr(i + ord('a'))
occurrence[i] -= 1
i += 1
k += 1
i -= 1
return ''.join(res[:k])
n = 3
string = "pqr"
print(get_nth_permute(string, n))
ইনপুট
"pqr"
আউটপুট
qpr
