عد أزواج الانقلاب بالدمج: المقارنة الصارمة وتكرار القيم

زوج فهارس في ترتيب الأصل

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

شرط الفهارس هو أن i أصغر من j، وشرط القيم أن قيمة i أكبر من قيمة j. لا نعد الزوج معكوس الاتجاه مرة أخرى، ولا نستعمل الموضع نفسه مع نفسه. كما لا نحتاج أن يكون الموضعان متجاورين؛ قد يقع بينهما عناصر أخرى. لذلك عدد الانقلابات ليس مجرد عدد المواضع التي يتجاوز فيها عنصر جاره التالي.

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

[1]

الأصل اثنان وخمسة وواحد واثنان وأربعة

قيم الأصل من الموضع صفر إلى أربعة هي 2 ثم 5 ثم 1 ثم 2 ثم 4. عند الموضع صفر، تتجاوز القيمة 2 الرقم 1 في الموضع اثنين، فنجد الزوج صفرًا مع اثنين. وعند الموضع واحد، تتجاوز 5 قيم المواضع اثنين وثلاثة وأربعة، فنجد ثلاثة أزواج إضافية. لا نجد زوجًا آخر يحقق الشرطين.

الأزواج الأربعة إذن صفر مع اثنين، وواحد مع اثنين، وواحد مع ثلاثة، وواحد مع أربعة. قيمها على الترتيب 2 مع 1، و5 مع 1، و5 مع 2، و5 مع 4. حفظنا الفهارس في الفحص اليدوي كي نميز الظهورات، لأن القيمة 2 موجودة في الأصل مرتين لكن لكل ظهور علاقات مختلفة مع ما يليه.

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

المساواة لا انقلاب

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

ولهذا يختار الدمج قيمة اليسار عند التعادل دون زيادة العداد. في آخر دمج لمثالنا، تأتي 2 من اليسار مقابل 2 من اليمين، فتخرج الأولى وتبقى الثانية لدورها. لا نحسب وجود عنصرين متساويين دليلًا أن أحدهما سبق الآخر بترتيب عددي خاطئ، ولا نحذف أحد الظهورين من الناتج بحجة أنه لم يضف انقلابًا.

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

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

نقسم أصلنا ذي خمسة عناصر إلى يسار فيه 2 ثم 5، ويمين فيه 1 ثم 2 ثم 4. كل جزء مرتب تصاعديًا، لذلك عدد الأزواج الداخلية في كل منهما صفر. الانقلابات الأربعة كلها بين عنصر يساري وعنصر يميني في هذا المستوى. يفيد المثال في رؤية العد العابر، لكنه لا يعني أن الأزواج الداخلية صفر في كل تقسيم.

في مثال مستقل من 5 ثم 1 ثم 4 ثم 2 ثم 6 ثم 2، يحوي اليسار الأول 5 مع 1 و5 مع 4، فيكون عدده الداخلي اثنين. واليمين 2 ثم 6 ثم 2 يحوي الزوج 6 مع 2، فيكون عدده واحدًا. توجد أيضًا أربعة أزواج عابرة بينهما، فيصبح المجموع سبعة. الأنواع الثلاثة تحتاج حفظًا منفصلًا حتى لا نفقد واحدًا منها.

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

الدمج وبقية اليسار

حين يكون رأس اليمين أصغر من رأس اليسار، فإنه أصغر أيضًا من بقية اليسار التي لم تخرج بعد، لأن الجزء الأيسر مرتب. وكل عناصر هذا اليسار جاءت قبل عناصر اليمين في تقسيم الأصل. لذلك يولد العنصر اليميني الحالي زوج انقلاب مع كل عنصر يساري باقٍ، لا مع الرأس الذي قارناه وحده.

نضيف عدد البقية، وهو طول اليسار ناقص موضع القراءة فيه. في أصلنا، يصل الرأس 1 في اليمين مقابل 2 في اليسار، فتتبقى القيمتان 2 و5، ونضيف اثنين: الزوج 2 مع 1 والزوج 5 مع 1. لو أضفنا واحدًا فقط لكانت النتيجة ناقصة، مع أن ترتيب القائمة الناتجة قد يظل صحيحًا.

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

تتبع نصفي اثنين وخمسة وواحد واثنين وأربعة

نبدأ باليسار 2 و5 واليمين 1 و2 و4. نسحب 1 من اليمين ونزيد العداد العابر إلى اثنين. ثم يتعادل 2 اليسار مع 2 اليمين، فنأخذ اليسار دون زيادة. يبقى رأس اليسار 5، فنأخذ 2 اليمين ونضيف واحدًا، ثم 4 اليمين ونضيف واحدًا آخر. بعد نفاد اليمين نضيف 5 المتبقية.

تصير النسخة المرتبة 1 ثم 2 ثم 2 ثم 4 ثم 5، والعد العابر أربعة. ومع صفر داخل اليسار وصفر داخل اليمين يكون العدد النهائي أربعة. هذه الخطوات تشرح ظهور العدد من القيم والمواضع، لا من عدد مرات استدعاء الدالة أو عدد الصفوف التي ظهرت في الناتج.

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

عرض الرسم بالحجم الكامل

عدم العد مرتين

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

والزوج العابر يعد عند سحب عنصره اليميني الأصغر. كل عنصر يميني يسحب مرة واحدة في الدمج، وكل إضافة تصف علاقاته مع بقية يسار معينة وقت تلك الخطوة. لا نكرر العد عندما تخرج عناصر اليسار المتبقية لاحقًا، لأن هذه العلاقات دخلت العداد بالفعل عند مرور الطرف اليميني.

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

القائمة المرتبة ليست قائمة الأزواج

ناتج دالتنا يحوي count وsorted_values، لكنه لا يحوي كل أزواج الفهارس التي حسبها. في المثال يرجع أربعة ونسخة 1 ثم 2 ثم 2 ثم 4 ثم 5. يمكن أن تساعد هذه النسخة في دمج المستوى الأعلى أو فحص الفرز، لكنها لا تعيد من نفسها أن أول 2 كان في الموضع صفر والثانية في ثلاثة.

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

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

الكود الأصلي ومخرج العدد والنسخة

الدالة التالية تقبل تتابعًا من أعداد int العادية وترجع عدد الانقلابات ونسخة مرتبة في tuple. ترفض bool والعشريات والنصوص بدل تحويلها إلى ترتيب آخر ضمنيًا. تحفظ نسخة من المدخل ثم تقسّم الأجزاء، وتوقف التكرار عند جزء فارغ أو مفرد، وتجمع العددين الداخليين والعابر عند الدمج.

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

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

def inversion_report(values):
    data = tuple(values)
    if any(type(value) is not int for value in data):
        raise TypeError("integer sequence required")
    def sort_count(part):
        if len(part) < 2:
            return part, 0
        middle = len(part) // 2
        left, left_count = sort_count(part[:middle])
        right, right_count = sort_count(part[middle:])
        output = []
        i = j = cross_count = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                output.append(left[i])
                i += 1
            else:
                output.append(right[j])
                cross_count += len(left) - i
                j += 1
        output.extend(left[i:])
        output.extend(right[j:])
        return tuple(output), left_count + right_count + cross_count
    ordered, count = sort_count(data)
    return {"count": count, "sorted_values": ordered}

الفارغ والمنفرد والمتناقص

التتابع الفارغ لا يحوي زوج فهارس، فيكون العدد صفرًا والنسخة المرتبة فارغة. والعنصر المفرد يبقى كما هو مع عدد صفر أيضًا، لأن شرط i قبل j لا يملك موضعين مختلفين. لا نخلط وجود قيمة سالبة في العنصر الوحيد بوجود انقلاب؛ التعريف يحتاج علاقة بين ظهورين، لا علامة قيمة منفردة.

وفي القائمة 3 ثم 2 ثم 1 توجد ثلاثة أزواج انقلاب: الأول مع الثاني والثالث، والثاني مع الثالث. هذه القائمة ذات ثلاث قيم مختلفة متناقصة تبلغ عدد كل أزواجها، وهو ثلاثة. عمومًا لا يمكن أن يتجاوز العدد عدد أزواج الفهارس المختلفة ذات الاتجاه الواحد، مع إمكان انخفاضه بسبب التعادلات أو ترتيب القيم.

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

العدد والتبديلات يحتاجان عقدًا

عدد أزواج الانقلاب لا يساوي تلقائيًا أقل عدد تبديلات بين موضعين كيفما اخترناهما. في 3 ثم 2 ثم 1، تبديل الأول والأخير مرة واحدة يعطي 1 ثم 2 ثم 3، بينما عدد الانقلابات ثلاثة. هذا مثال مستقل صغير يبين لماذا لا نكتب عدد تبديلات في عنوان حقل يحسب أزواجًا إلا بعد تحديد العمليات المسموحة.

إذا حصرنا التبديل في عنصرين متجاورين، يمكن ترتيب المثال بثلاث خطوات: 2 ثم 3 ثم 1، وبعدها 2 ثم 1 ثم 3، ثم 1 ثم 2 ثم 3. كل خطوة اختارت جارين مخالفين وقللت علاقة مباشرة واحدة في هذا المسار. يختلف هذا العقد من تبديل طرفين بعيدين قد يغير عدة علاقات دفعة واحدة.

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

مرجع مقارنة كل زوج أصلي

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

نفذنا المقارنة على تتابعات بأطوال من صفر إلى سبعة وقيم من سالب 1 وصفر و2. ونراجع أيضًا أن النسخة المرتبة من الدالة تطابق فرز القيم تصاعديًا في المرجع، مع حفظ عدد كل ظهور. توافق العداد لا يكفي إذا أسقطت الدالة قيمة، كما أن نجاح الفرز لا يكفي إذا عدت تعادلًا أو فاتتها أزواج عابرة.

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

كلفة العد وحجم إخراج الأزواج

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

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

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

[1]

بطاقة النتيجة والمقارنة والنسخة

يمكن وصف البطاقة بالأصل 2 ثم 5 ثم 1 ثم 2 ثم 4، وبمقارنة صارمة تصاعدية وفهارس تبدأ من صفر. نكتب العدد أربعة والأزواج الصغيرة التي تحققها للشرح، مع بيان أن الدالة المعروضة ترجع العدد والنسخة المرتبة فقط. ونضيف النسخة 1 ثم 2 ثم 2 ثم 4 ثم 5 كي نراجع حفظ القيم والتكرار.

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

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