هل هناك نظرية تتعلق بحساب العدد الإجمالي للكائن الفردي مع اختيار واحد عشوائيا؟

Question

تحدي خوارزمي مشترك هو توليد كائن من نوع معين، بشكل موحد عشوائيا. على سبيل المثال، توليد التقليب العشوائي الحجم $ k $ من مجموعة معينة من $ n $ الأحرف، كما هو الحال في هذا السؤال .

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

على سبيل المثال، لنفترض أنني أريد إنشاء سلسلة عشوائية من $ n $ $ 1 $ s and $ 0 $ s، حيث لا يوجد اثنان من $ 1 $ s. يمكنني أن أبدأ عن طريق ترك $ A [n] $ يكون عدد هذه التسلسلات، ومراقبة ذلك $$ a [n]= a [n-1] + a [n-2].

(هذه هي علاقة Fibonacci.) هذا يسمح لي بحساب جدول $ A [i] $ for $ i= 1 $ $ i= n $ . الآن إذا كنت ترغب في توليد هذا التسلسل عشوائي، كل ما علي فعله هو:

الخطوة 1: إنشاء قيمة عشوائية $ r $ من $ 1 $ إلى $ a [n] $ .

الخطوة 2: استخدم علاقة التكرار لتحديد موقع المصطلح الفرعي الذي يتوافق مع $ r $ التسلسل:

• إذا كان $ r \ le a [n-1] $ ، ابحث بشكل متكرر أن $ r $ < / span> th التسلسل الذي يتم حسابه بواسطة $ A [N-1] $ ، وملحق $ 0 $ .

• li>

  خلاف ذلك، إذا $ A [N-1] ، تعيين $ r '= r - a [n-1] $ ، والعثور بشكل متكرر على $ r' $ تسلسل TH عد $ A [N-2] $ ، وإلحاق $ 01 $ .

ما يبدو أنه يحدث هنا هو أنه، مع إعطاء أي علاقة تكرار ل $ a [n] $ ، يمكنني تحويل هذا إلى خوارزمية متكررة التي ترجع $ r $ الكائن العدل حسب $ a [n] $ . أفترض أن هذا معروف جيدا، لذلك سأكون مهتما بأي مراجع أو نتائج كلاسيكية حول هذا الموضوع. على وجه الخصوص، هذا ليس فقط محددا للمثال $ A [n] $ ، ولكن يجب أن يكون صحيحا ل أي علاقة تكرار مرضية خصائص.

أيضا، أعتقد أن هذا قد يرتبط ببعض الأبحاث حول الاختبار العشوائي.

Answer 1

تعرف هذه باسم الترتيب والوظائف غير المرفوعة .أنت على حق في المراسلات بين علاقات تكرار العد والخوارزميات غير المرغوبة.