التباديل والتوافيق وتطبيقاتها في علوم الحاسب

Combinations and Permutations in computer science

بسم الله الرحمن الرحيم

اعتقد أن أغلبنا قد درس عن التباديل والتوافيق في الرياضيات ولكن لا يعلم ما هي استخداماتها في البرمجة ولكي اعبر لك عن اهميتها سأطرح الأسئلة التالية :
كم رقم ثنائي بطول A خانات يمكننا تكوينه إذا كان يحتوي على B واحدات بين خاناته
كم رقم يمكننا تكوينه إذا كان بامكاننا فقط استخدام A عدد والتكرار غير مسموح
ما هو عدد التباديل التي يمكن بها إعادة تشكيل الكلمة "CALCULUS" .
ما هو عدد الطرق التي يمكن بها توزيع A رسالة على B مراسلين بحيث كل مراسل يأخذ رسالة على الأقل ؟
ما هو عدد حلول هذه المعادلة : X₁ + X₂ + X₃ + X₄ = N بحيث (X >= 0) .

حسنا لنبدأ .

قاعدة الجمع :
بفرض كان لدينا N عنصر (m₁ , m₂ , ...... , m_n ) وكل عنصر من نوع مختلف ، فإن عدد الطرق التي يمكننا بها اختيار أي عنصر هو W
W = m₁ + m₂ + ..... + m₃

قاعدة الضرب :
بفرض كان لدينا N عنصر (m₁ , m₂ , ...... , m_n ) وكل عنصر من نوع مختلف ، فإن عدد الطرق التي يمكننا بها اختيار أي عنصر من كل نوع هو W
W = m₁ * m₂ * .... * m_n

نعلم جميعا أن عدد التبديلات لـ n عنصر خلال m حدث مع السماح بتكرار العنصر هو n^m

وعدد التبديلات لـ n عنصر خلال m حدث مع عدم السماح بتكرار العنصر هو n * (n-1) * (n-2) * .... * (n-m+1

التباديل :

( سحب r عنصر على التوالي من n إذا كان الترتيب مهم )

مثلا إن عدد التبديلات في حال تم السحب مرتين (حدثين) من العناصر (x , y , z) إذا كان الترتيب مهما :
x y  ,  x z  ,  y x  ,  y z  ,  z x  ,  zy

(الترتيب مهما : أي يمكننا كتابة x y  و y x  أما إذا كان الترتيب غير مهم فتكفي واحدة منهما)

أي أن عدد التبديلات 3 * 2 = 6 أي n * (n-1

• فعدد التباديل لـ n عنصر خلال k حدث هو 
  
  
   
• عدد التبديلات عندما نختار k عنصر من n عندما يجب عدم اختيار s عنصر هو

• عدد التبديلات عند اختيار k عنصر إذا كان يجب اختيار s عنصر هو

التوافيق :

( سحب r عنصر معا من n إذا كان الترتيب غير مهم )

مثلا إن عدد التوافيق في حال تم السحب مرتين (حدثين) من العناصر (x , y , z) إذا كان الترتيب غير مهم :
x y  ,  x z  ,  y z

الناتج هو (1 * 2 ) / ( 2 * 3 )
 

• عدد التوافيق في حالة سحب k عنصر من n عنصر هو

• عدد طرق توزيع n كرة في r صندوق بحيث كل صندوق يحوي على كرة على الأقل

• عدد التوافيق في حال التكرار مسموح

• عدد حول المعادلة X₁ + X₂ + .... + X_r = N في حال (X > 0 ) هو

وهو ما يشبه حالة توزيع n  كرة في r صندوق بحيث كل صندوق يحوي كرة على الأقل
أما في حال ( X >= 0 ) فعدد الحلول هو

• عدد التبديلات عند اختيار r₁ عنصر من النوع A و r₂ عنصر من النوع B وووو ..... و r_n عنصر من النوع K هو
   

أصبح الأن بإمكاننا حل الأسئلة السابقة :

عدد التشكيلات لرقم ثنائي بطول A يحوي على B وحدات بين خاناته هو C_A,B

عدد الأرقام التي يمكن تشكيلها من A عدد بغير تكرار هو !A
 

عدد التباديل التي يمكن تشكيلها من كلمة CALCULUS هي 

عدد الطرق التي يمكن بها توزيع A رسالة على B مراسلين بحيث كل مراسل يأخذ رسالة على الأقل هو عدد حول المعادلة X₁ + X₂ + .... + X_B = A في حال (X > 0 )

ويعد إيجاد عدد الطرق في الشبكات من أهم التطبيقات لها .
وإليك المثال التالي :

أ . ما هي عدد الطرق الممكنة في الشبكة للوصول إلى F من S ؟
ب . ما هي عدد الطرق الممكنة للوصول إلى F من S إذا علمت أنه يجب المرور من M ؟
جـ . ما هي عدد الطرق الممكنة للوصول إلى F من S إذا علمت أنه يجب عدم المرور من M ؟

 ~ أ . الطريق من S إلى  F  يمثل سلسلة من الخطوات يمنة R وإلى الأسفل D ، وهي 7 خطوات بالتحديد ( 4D و 3R ) ، فمثلا السلسلة "RDDRDRD" تعتبر من أحد الحلول .
فعدد الطرق الممكنة هي عدد السلاسل التي طولها 7 وتحوي 3R (و 4D بالطبع )
W = C(7 , 3) =35
W = 7! / ( 3! * 4!) = 35

~ ب . نقسم الطريق إلى طريقين من S إلى M و من M إلى F
C(3 , 1) * C(4 , 2) = 18

~ جـ . الحل إما : 17 = 18 - 35
أو يمكننا القول أن عدم المرور ب M يستوجب المروةر بالنقاط الأخرى ( u,v,w )
C(3,0)* C(4,3)   +  C(3,2)*C(4,1)  +  C(3,3)*C(4,0) = 17


شكرا لمتابعتكم .. والسلام عليكم ورحمة الله وبركاته