পাইথন প্রোগ্রাম: লিস্ট থেকে K-র চেয়ে কম ডিফারেন্স থাকা এলিমেন্ট সরানো

সর্ট করা লিস্ট থেকে যেসব এলিমেন্টের পার্থক্য (ডিফারেন্স) K-র চেয়ে কম, সেগুলো সরিয়ে শুধু পর্যাপ্ত দূরত্ব বজায় রাখা এলিমেন্টগুলো রাখার জন্য সর্টিং এবং হাইল লুপ ব্যবহার করা হয়।

উদাহরণ

my_list = [13, 29, 24, 18, 40, 15]
K = 3
print("মূল লিস্ট:", my_list)
print("K =", K)

# ১. সর্ট করা
my_list = sorted(my_list)
print("সর্টেড:", my_list)

# ২. K-র চেয়ে কম ডিফারেন্স olan এলিমেন্ট সরানো
i = 0
while i < len(my_list) - 1:
    if my_list[i] + K > my_list[i + 1]:
        # ডিফারেন্স < K, পরবর্তী এলিমেন্ট মুছে ফেলা
        del my_list[i + 1]
    else:
        i += 1

print("ফলাফল:", my_list)

আউটপুট

মূল লিস্ট: [13, 29, 24, 18, 40, 15]
K = 3
সর্টেড: [13, 15, 18, 24, 29, 40]
ফলাফল: [13, 18, 24, 29, 40]

স্টেপ-বাই-স্টেপ

সর্টেড: [13, 15, 18, 24, 29, 40]
i=0: 13+3=16 > 15? হ্যাঁ → 15 মুছে ফেলা → [13, 18, 24, 29, 40]
i=0: 13+3=16 > 18? না → i=1
i=1: 18+3=21 > 24? না → i=2
i=2: 24+3=27 > 29? না → i=3
i=3: 29+3=32 > 40? না → i=4 (লুপ শেষ)

দ্রষ্টব্য: এই অ্যালগরিদম "লালচী" (greedy)

এটি সবসময় অপ্টিমাল সমাধান দেয় না (ম্যাক্সিমাম সাবসেট পাওয়া NP-hard সমস্যা)। এটি শুধু সিকোয়েন্সিয়াল চেক করে।

অপ্টিমাল সমাধান (Dynamic Programming / Backtracking)

def max_subset_min_diff(arr, k):
    """সর্বোচ্চ আকারের সাবসেট যেখানে যেকোনো দুটি এলিমেন্টের ডিফারেন্স >= k"""
    arr = sorted(arr)
    n = len(arr)
    
    # DP: dp[i] = i-ই ইন্ডেক্স পর্যন্ত ম্যাক্স সাবসেট সাইজ
    dp = [1] * n
    prev = [-1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[i] - arr[j] >= k and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    
    # রিকনস্ট্রাক্ট
    max_idx = dp.index(max(dp))
    subset = []
    while max_idx != -1:
        subset.append(arr[max_idx])
        max_idx = prev[max_idx]
    return subset[::-1]

print(max_subset_min_diff([13, 29, 24, 18, 40, 15], 3))
# [13, 18, 24, 29, 40] (এই কেসে greedy-ও একই ফলাফল দেয়)