الاختيار العشوائي الموزون مع وبدون استبدال

استجابة لتحدي البرمجة، نسعى للحصول على خوارزميات فعالة للاختيار العشوائي الموزون من القائمة، مع أو بدون استبدال.

الاختيار الموزون مع الاستبدال

طريقة الاسم المستعار . تقوم هذه التقنية بإنشاء مجموعة من الصناديق متساوية الحجم لكل عنصر مرجح. ومن خلال استخدام عمليات البت، يمكننا فهرسة هذه الصناديق بكفاءة دون اللجوء إلى البحث الثنائي. يخزن كل صندوق نسبة مئوية واحدة تمثل الحد الفاصل بين العناصر الموزونة الأصلية.

تنفيذ طريقة الاسم المستعار

تطبيع الأوزان: قسمة كل وزن على الإجمالي ليصبح المجموع 1.0.
تحديد أصغر قوة 2 أكبر من أو تساوي الرقم من العناصر (هنا، 8).
2. خصص قسمًا فارغًا لكل عنصر.
4. كرر الخطوات التالية حتى يتم توزيع جميع الأوزان:
   ضع أكبر قدر من العنصر ذو الوزن المتبقي الأقل في قسم فارغ.
   • إذا لم يتم ملء القسم، أضف العنصر الأثقل المتبقي.

p1: {a, 1.0}
• p2: {a, b, 0.6

تحديد وقت التشغيل

1. قم بتحويل الرقم العشوائي للعثور على فهرس القسم.
2. إذا تم تقسيم القسم، استخدم الجزء العشري من الرقم الذي تم إزاحته بتًا لتحديد العنصر الذي سيتم إرجاعه.

بينما الخوارزميات مثل طريقة الخزان الموزون الموجودة للاختيار غير الموزون دون استبدال، تظل هذه المشكلة دون حل.