র‍্যান্ডোমাইজড অ্যালগরিদম — লাস ভেগাস বনাম মন্টি কার্লো

import random

def randomized_select(rng, arr, k):
    # arr-এর মধ্যে k-তম ক্ষুদ্রতম (0-ইনডেক্সড) এলিমেন্ট বের করা -- সবসময় সঠিক, রানটাইম র‍্যান্ডম
    arr = list(arr)
    lo, hi = 0, len(arr) - 1
    comparisons = 0
    while True:
        if lo == hi:
            return arr[lo], comparisons
        pivot_idx = rng.randint(lo, hi)          # -- এই লাইনটাই একমাত্র র‍্যান্ডম সিদ্ধান্ত
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            comparisons += 1
            if arr[i] < pivot:
                arr[i], arr[store] = arr[store], arr[i]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]
        if store == k:
            return arr[store], comparisons
        elif k < store:
            hi = store - 1
        else:
            lo = store + 1

master_rng = random.Random(2026)
n = 50
k = n // 2   # মিডিয়ানের কাছাকাছি
test_arr = [master_rng.randint(-1000, 1000) for _ in range(n)]
true_answer = sorted(test_arr)[k]

comparison_counts = []
all_correct = True
for seed in range(20):
    sort_rng = random.Random(seed)
    result, c = randomized_select(sort_rng, test_arr, k)
    comparison_counts.append(c)
    if result != true_answer:
        all_correct = False
        print(f"seed {seed}: MISMATCH! পেয়েছি {result}, প্রত্যাশিত {true_answer}")
    assert result == true_answer

print(f"একই অ্যারেতে ২০টি ভিন্ন seed-এ randomized_select চালানো হলো (একই k={k} খুঁজতে):")
print(f"সবগুলো রানই সঠিক উত্তর ({true_answer}) দিয়েছে: {all_correct}")
print(f"\nতুলনার সংখ্যা -- সর্বনিম্ন: {min(comparison_counts)}, সর্বোচ্চ: {max(comparison_counts)}, "
      f"গড়: {sum(comparison_counts)/len(comparison_counts):.1f}")
print("লক্ষ্য করুন: আউটপুট সবসময় একই (সঠিক), কিন্তু তুলনার সংখ্যা (রানটাইম) seed অনুযায়ী পাল্টায় -- এটাই লাস ভেগাসের সংজ্ঞা।")

import random

def is_balanced_exact(bits):
    N = len(bits)
    ones = sum(bits)
    return abs(ones / N - 0.5) <= 0.05

def is_balanced_monte_carlo(rng, bits, sample_size):
    # শুধু sample_size টি র‍্যান্ডম পজিশন দেখে সিদ্ধান্ত -- সম্পূর্ণ স্ট্রিং স্ক্যান করা হয় না
    N = len(bits)
    positions = rng.sample(range(N), sample_size)
    ones_in_sample = sum(bits[i] for i in positions)
    fraction = ones_in_sample / sample_size
    return abs(fraction - 0.5) <= 0.05

rng = random.Random(1729)
N = 3000
sample_size = 300
p_values = [0.25, 0.38, 0.47, 0.50, 0.53, 0.62, 0.75]   # কিছু স্পষ্ট ব্যালেন্সড/আনব্যালেন্সড, কিছু বাউন্ডারির কাছাকাছি

num_trials = 300
mismatches = 0
for _ in range(num_trials):
    p = rng.choice(p_values)
    bits = [1 if rng.random() < p else 0 for _ in range(N)]
    exact = is_balanced_exact(bits)
    mc = is_balanced_monte_carlo(rng, bits, sample_size)
    if exact != mc:
        mismatches += 1

error_rate = mismatches / num_trials
print(f"মোট ট্রায়াল: {num_trials}, sample_size={sample_size} (পূর্ণ N={N}-এর মাত্র {100*sample_size/N:.0f}%)")
print(f"এক্স্যাক্ট চেক ও মন্টি কার্লো চেক ভিন্নমত হয়েছে এমন ট্রায়াল: {mismatches}")
print(f"সৎভাবে গণনা করা এরর রেট: {error_rate:.3f} ({100*error_rate:.1f}%)")
print("\nএটি লাস ভেগাস নয় -- মাঝেমধ্যে ভুল উত্তর আসে (বিশেষত p=0.47/0.53-এর মতো বাউন্ডারির কাছাকাছি কেসে),")
print("কিন্তু রানটাইম সবসময় O(sample_size)-এ বাউন্ডেড, N যত বড়ই হোক না কেন।")