পাইথনে দिये गये সংখ্যা গুলো থেকে সম্ভাব্য সর্বোচ্চ সংখ্যা বানানো

সমস্যা বিবরণ

একটি সংখ্যা লিস্ট দেওয়া আছে। এই সংখ্যা গুলোকে কোনো অর্ডারে সাজিয়ে সম্ভাব্য সর্বোচ্চ সংখ্যা বানাতে হবে।

উদাহরণ

Input:  [45, 35, 138, 43, 67]
Output: 67454335138

পদ্ধতি ১: পারমুটেশন (Brute Force - ছোট ইনপুটের জন্য)

সকল পারমুটেশন জেনারেট করে সর্বোচ্চ বের করুন। O(n!) জটিলতা।

import itertools

numbers = [45, 35, 138, 43, 67]
result = []

for perm in itertools.permutations(str(n) for n in numbers):
    result.append(''.join(perm))

maximum = max(result, key=int)
print(int(maximum))  # 67454335138

পদ্ধতি ২: কাস্টম সর্টিং (দক্ষ - O(n log n))

দুই সংখ্যা a ও b এর জন্য, ab > ba হলে a আগে আসবে। এই কাস্টম কমপারেটর দিয়ে সর্ট করুন।

from functools import cmp_to_key

numbers = [45, 35, 138, 43, 67]

def compare(a, b):
    # ab > ba হলে a আগে আসবে (descending order)
    if str(a) + str(b) > str(b) + str(a):
        return -1
    return 1

result = sorted(numbers, key=cmp_to_key(compare))
result_str = ''.join(str(x) for x in result)
print(int(result_str))  # 67454335138

কমপারেটর লজিক ব্যাখ্যা

a=67, b=45 → "6745" > "4567" → 67 আগে আসবে
a=138, b=43 → "13843" < "43138" → 43 আগে আসবে
এই লজিক ট্রানজিটিভ (transitive), তাই সর্টিং কাজ করে

এজ কেস হ্যান্ডলিং

# সব শূন্য হলে
numbers = [0, 0, 0]
result = ''.join(str(x) for x in sorted(numbers, key=cmp_to_key(compare)))
print(int(result))  # 0 (না হলে "000" আসবে)

উপসংহার

কাস্টম কমপারেটর দিয়ে সর্টিং হলো অপ্টিমাল সমাধান
functools.cmp_to_key কমপারেটর ফাংশনকে সর্ট কীতে কনভার্ট করে
লিডিং জিরো হ্যান্ডল করতে int() বা লজিক যোগ করুন