ما معنى Combination في الخوارزميات وهياكل البيانات؟ شرح عملي مع الفرق عن Permutation

الـCombination (التوفيقة أو التوليفة) في الخوارزميات تعني: اختيار عدد من العناصر من مجموعة أكبر دون أن يهمّك ترتيبها. أي أن اختيار الحرفين A ثم B هو نفسه اختيار B ثم A — كلاهما "التوفيقة {A, B}" وتُحسب مرة واحدة فقط. هذه النقطة بالذات (تجاهل الترتيب) هي جوهر المفهوم، وهي ما يميّزه عن التباديل (Permutations) التي كثيراً ما يخلط بينها المبتدئون.

خذ مجموعة الحروف {A, B, C} واختر منها حرفين. التوافيق الممكنة هي: {A,B} و{A,C} و{B,C} — ثلاث توافيق فقط. لو كان الترتيب مهماً (تباديل) لأصبحت ستّ حالات: AB, BA, AC, CA, BC, CB. تذكُّر هذا الفرق يوفّر عليك أخطاءً كثيرة في حلّ المسائل.

الفرق بين Combination و Permutation

هذا هو الالتباس الأكثر شيوعاً، وأسهل طريقة لحسمه هي سؤال واحد: هل يغيّر تبديل ترتيب العناصر النتيجة؟ إذا كان الجواب نعم فأنت أمام تبديل (Permutation)، وإذا كان لا فهو توفيقة (Combination).

المعيار	Combination (توفيقة)	Permutation (تبديل)
هل الترتيب مهم؟	لا	نعم
{A,B} و{B,A}	نفس الحالة	حالتان مختلفتان
العدد الكلي	أصغر	أكبر
القانون	‏n! / (r! × (n−r)!)	‏n! / (n−r)!
مثال واقعي	اختيار 3 لاعبين للفريق	ترتيب أول 3 مراكز في سباق

القاعدة العملية: كلما احتوى وصف المسألة على كلمات مثل "اختَر مجموعة" أو "أيّ عناصر" فهي غالباً توافيق؛ وكلما احتوى على "رتِّب" أو "المركز الأول والثاني" فهي تباديل.

قانون الحساب: nCr

عدد التوافيق لاختيار r عنصراً من n عنصراً يُرمز له بـ C(n, r) أو nCr، ويُحسب:

C(n, r) = n! / ( r! × (n − r)! )

مثال: عدد طرق اختيار لجنة من 3 أشخاص من بين 5 = C(5,3) = 120 / (6 × 2) = 10. لاحظ خاصية مفيدة: C(n, r) = C(n, n−r)، لأن اختيار العناصر التي "تدخل" يكافئ تحديد العناصر التي "تخرج". وهناك متطابقة باسكال المفيدة في البرمجة الديناميكية: C(n, r) = C(n−1, r−1) + C(n−1, r).

نصيحة عملية: لا تحسب المضروب (factorial) كاملاً في الكود ثم تقسم، فقيمة !n تتضخّم بسرعة وتسبّب overflow حتى مع أعداد صغيرة نسبياً. بدلاً من ذلك اضرب واقسم تدريجياً، أو استخدم مثلث باسكال (مصفوفة برمجة ديناميكية) لحساب القيم دون الوصول إلى أرقام عملاقة.

كيف تولّد كل التوافيق برمجياً

في المقابلات البرمجية ومسائل مثل LeetCode 77 (Combinations)، لا يُطلب منك العدد فقط، بل توليد كل التوافيق فعلياً. الأسلوب القياسي هو التتبّع الخلفي (Backtracking) العودي، مع فكرة أساسية: لتجنّب التكرار وتجاهل الترتيب، تقدّم دائماً إلى الأمام ولا تعود إلى عنصر سبق تجاوزه (نستخدم مؤشر بداية start).

الخطوات:

1. ابدأ بمسار فارغ ومؤشر يشير إلى أول عنصر.
2. أضف العنصر الحالي إلى المسار.
3. استدعِ الدالة عودياً بدءاً من العنصر التالي (وليس من البداية) — هذا ما يمنع تكرار {A,B} و{B,A}.
4. عندما يبلغ طول المسار العدد المطلوب r، سجّل التوفيقة.
5. تراجع (احذف آخر عنصر) وجرّب العنصر التالي.

def combinations(items, r):
    result, path = [], []
    def backtrack(start):
        if len(path) == r:
            result.append(path.copy())
            return
        for i in range(start, len(items)):
            path.append(items[i])
            backtrack(i + 1)   # i+1 وليس start: يمنع التكرار وتجاهل الترتيب
            path.pop()
    backtrack(0)
    return result

معظم اللغات توفّر أدوات جاهزة أيضاً، مثل itertools.combinations في بايثون، ويُفضَّل استخدامها في الإنتاج بدل كتابة الخوارزمية يدوياً.

أين تظهر التوافيق في المسائل الفعلية

• توليد المجموعات الجزئية (Subsets): مجموعة القوة (Power Set) هي في جوهرها اتحاد كل التوافيق بأطوال 0 حتى n.
• مسائل التحسين والبحث: تجربة كل مجموعة ممكنة من الخيارات، كاختيار مجموعة عناصر لا يتجاوز وزنها حداً معيناً.
• الاحتمالات والإحصاء: حساب احتمالات سحب عناصر من عيّنة.
• الاستعلامات وتحليل البيانات: توليد مجموعات الميزات (features) لاختبارها في نماذج التعلم الآلي.

انتبه إلى التعقيد: عدد التوافيق ينمو بشكل هائل (أُسّي في أسوأ الحالات)، لذا توليد "كل" التوافيق يصلح فقط عندما تكون n صغيرة؛ ومع القيم الكبيرة تحتاج إلى تقليم (pruning) أو أسلوب مختلف كلياً.

الأسئلة الشائعة

هل C(n, 0) له معنى؟ نعم، ويساوي 1 دائماً — هناك طريقة واحدة لاختيار "لا شيء": المجموعة الفارغة.

لماذا نستخدم start أو i+1 في كود التوليد؟ لأنه يضمن أن كل عنصر يأتي بعد سابقه في الترتيب، فلا تتولّد {B,A} بعد {A,B}. هذا بالضبط ما يترجم "تجاهل الترتيب" إلى كود.

متى أستخدم التباديل بدل التوافيق؟ عندما يغيّر ترتيب العناصر معنى النتيجة: أرقام سرية (PIN)، ترتيب مراكز، جدولة مهام بترتيب محدّد.

هل الحساب اليدوي للمضروب آمن في الكود؟ لا يُنصح به؛ استخدم الضرب التدريجي أو مثلث باسكال لتفادي تضخّم الأعداد وتجاوز حدود النوع (overflow).