partition تثبت قيمة kth في موضع فرزها، وتترك ترتيب الطرفين غير محدد. [1] نختبر المعنى بأعداد مختلفة.
افصل الرتبة عن الفرز الكامل
تثبت partition قيمة kth في موضعها عند الفرز، لكن ترتيب العناصر على جانبيها غير محدد. [1]
نؤلف a=[10,−2,13,4,1,7]. فرزها التصاعدي الكامل هو [−2,1,4,7,10,13]. كل القيم مختلفة وبلا وحدة، وليست درجات فعلية. نختار الموضع k=2، فتكون قيمته في الفرز 4.
الترتيب p=[1,−2,4,13,7,10] يحتفظ بالأعداد الستة. قبل 4 تقع 1 و−2، وكلاهما أصغر منها؛ وبعدها 13 و7 و10، وكلها أكبر. لذلك يحقق شرط الفصل في نموذج الأعداد المختلفة، مع أن 1 تسبق −2 و13 تسبق 7.
نؤلف ترتيبًا آخر q=[−2,1,4,10,13,7]. يحقق الشرط نفسه والقيمة عند الموضع 2 هي 4 أيضًا، لكن ترتيب الطرف الأيمن مختلف. لم نحصل على p أو q من تنفيذ partition؛ اخترناهما لبيان أن الشرط يسمح بأكثر من ترتيب.
عد الفهرس من صفر
نرقم مواضع القائمة من صفر إلى خمسة. الموضع صفر يخص أول قيمة، و1 يخص الثانية، و2 يخص الثالثة. لهذا لا نساوي «ثالث أصغر قيمة» بالفهرس 3.
في المثال المرتب، تقع −2 عند صفر و1 عند 1 و4 عند 2 و7 عند 3. اختيار k=2 يعني 4، واختيار k=3 يعني 7. أما a الأصلية فتحتوي 13 عند موضعها 2؛ القيمة التي كانت هناك قبل إعادة الترتيب ليست تعريفًا للرتبة المطلوبة.
نتحقق بالعد: توجد قيمتان أصغر من 4، هما −2 و1. ومع اختلاف القيم، رتبة الفهرس من صفر تساوي عدد الأصغر من قيمة العنصر. إذا وضعنا 7 عند الموضع 2، فإن الأصغر منه ثلاث قيم؛ لا يحقق الرتبة المطلوبة، ولو بدا الجزء الأول مرتبًا.
مثلًا [−2,1,7,4,10,13] يفشل شرط الفصل عند k=2: تقع 4 بعد 7 رغم أنها أصغر. تساوي طول القائمة وبقاء الأعداد نفسها لا يكفي؛ نراجع القيمة عند الفهرس وما يقع على كل جانب.
اقرأ مجموعة الطرف دون ترتيبها
في p، أول ثلاث قيم هي [1,−2,4]. إذا رتبنا هذه القيم وحدها تصاعديًا، صارت [−2,1,4]، وهي أصغر ثلاث قيم من الأصل. لكن القراءة كما هي تبدأ عند 1، لا عند −2. الفصل يحدد المجموعة المطلوبة هنا ولا يجعل أول خانة هي الصغرى.
لأعداد مختلفة، لا يمكن أن يبقى عدد أصغر من المحور على الطرف الأيمن في ترتيب صحيح. وفي مثال k=2، توجد قيمتان أصغر، فتشغلان الخانتين اليسريين؛ مع المحور نحصل على ثلاث قيم. ترتيب الخانتين فيما بينهما سؤال إضافي.
يمكن عد الترتيبات التي يسمح بها نموذجنا: للقيمتين على اليسار ترتيبان، وللقيم الثلاث على اليمين ستة ترتيبات، مع بقاء 4 ثابتة. حاصل الضرب 2×6=12. تختار كل حالة ترتيبًا يساريًا ويمينيًا مستقلين. هذا عد للإمكانات، وليس وصفًا لخوارزمية المكتبة أو توزيع احتمالات مخرجاتها.
عمومًا، لطول n وقيمة محور ذات فهرس k ضمن أعداد مختلفة، يكون عدد هذه الترتيبات k!×(n−k−1)!. الفرز الكامل حالة واحدة منها. عند k=0 يكون الطرف الأيسر خاليًا، وعند k=n−1 يكون الأيمن خاليًا؛ نستخدم 0!=1 في العد.
حدود البرهان والفحص
حددنا سؤالنا بقائمة غير خالية من أعداد صحيحة مختلفة، وفهرس واحد يحقق 0≤k<n. لم نبحث في القيم المتساوية أو الفهارس السالبة أو طلب عدة فهارس رتبة معًا. شرط الأصغر والأكبر الصارم في نموذجنا يعتمد على اختلاف الأعداد.
نفذنا فحصًا مستقلاً لكل 873 تبديلًا من أطوال 1 إلى 6، ولكل فهرس قانوني داخل التبديل، فحصلنا على 5039 زوجًا. قارنّا متباينات الطرفين بمجموعتي القيم وبقيمة الرتبة المرتبة، وراجعنا مجموعة المقدمة وعدد الأصغر من المحور: ثلاثة فحوص لكل زوج.
ثم تحققنا من عدد الترتيبات الصحيحة لكل طول وفهرس، في 21 حالة عد، وأجرينا ستة فحوص خاصة للأمثلة. الإجمالي 3×5039+21+6=15144. هذه مراجعة رياضية محدودة للأطوال المذكورة؛ الصيغة العامة مشتقة من ترتيب عناصر الطرفين.
لم نشغل NumPy أو نتنبأ بترتيب محدد تخرجه خوارزميتها. ولم نفحص الأنواع المركبة أو NaN أو المحاور المتعددة أو الذاكرة والسرعة. نميز بين ترتيب جائز وفق الشرط وبين نتيجة تنفيذ فعلية؛ والأمثلة المعروضة تنتمي إلى الأول.
| الترتيب المؤلف | القيمة عند 2 | أول ثلاث قيم |
|---|---|---|
| p | 4 | 1، −2، 4 |
| q | 4 | −2، 1، 4 |
| فرز كامل | 4 | −2، 1، 4 |
| ترتيب يفشل الشرط | 7 | −2، 1، 7 |
للتوسع: الأبعاد والقطر والمنقول.
المراجع
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.