🐔 🌜 🤹 التوافقية في بيثون 👭 🚶 🐓

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

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

افترض أن لدينا سلسلة تتكون من أحرف مختلفة ونريد حساب جميع الطرق لإعادة ترتيب هذه الحروف بطريقة تحصل على سطر جديد. بالنسبة للموضع الأول في السطر ، يمكننا اختيار أحد الأحرف n التي لدينا ، والموضع الثاني واحد من الأحرف n - 1st وهكذا. نتيجة لذلك ، نحصل على المنتج n (n-1) ... * 1 = n! عدد التباديل للعناصر n بدون تكرار .

الآن تخيل أن عدد الأحرف في السلسلة محدود. لدينا أحرف n متوفرة ونريد حساب عدد طرق إنشاء سلسلة من الأطوال k منها ، حيث k <n ، يمكننا استخدام كل حرف مرة واحدة فقط. بعد ذلك ، يمكننا وضع أحد الأحرف n في الموضع الأول في السطر ، وواحد من الأحرف n-1 في الموضع الثاني وواحد من الأحرف n-k + 1 على الموضع k-th. سيكون العدد الإجمالي للخطوط مساوياً n (n - 1) (n - 2) ... (n - k + 2) (n - k + 1) = n! / (Nk)! عدد المواضع من n إلى k . إذا كان تفرد الحروف غير مطلوب ، فسنحصل على الصيغة n ... n n = n ^ k بعدد المواضع من n إلى k مع التكرار .

قبل ذلك ، قمنا بفرز التسلسلات مع مراعاة ترتيب العناصر ، وما إذا كان الأمر لا يهمنا. على سبيل المثال ، لدينا حلوى مختلفة ونريد اختيار k منها لإعطاءها لصديق ، و k <n. كم عدد الطرق المتاحة لاختيار الحلوى k من ن دون النظر إلى النظام؟ الجواب بسيط ، في البداية سنجد موضع n بواسطة k دون تكرار ، ولكن بعد ذلك ستتكرر نفس مجموعات الحلوى ذات الترتيب المختلف لتسلسلها. كيف العديد من الطرق لإعادة ترتيب الحلوى؟ هذا صحيح ، التقليب من عناصر k دون تكرار. الجواب النهائي: يتم تقسيم مواضع n بواسطة k على التباديل في k دون التكرار. الصيغة: $n! / (n-k)! / k!$ عدد توليفات n بواسطة k .

النظر في القضية أكثر تعقيدا ، لدينا صناديق ن كل منها يحتوي على العديد من الحلوى من نفس المذاق ، ولكن في صناديق مختلفة تختلف الأذواق. كم عدد الطرق المتاحة لتقديم هدية لصديق من الحلوى k ، وماذا يمكن أن يحدث نفس المذاق في أي عدد من المرات؟ نظرًا لأن الطلب لا يهم بالنسبة لنا ، فلنرتب حلويات الهدايا على النحو التالي: في البداية سيكون هناك حلويات متتالية من المذاق الأول ، ثم من المذاق الثاني وما إلى ذلك ، وسنضع المطابقات بين الحلوى ذات الأذواق المختلفة إذا تغيبت الحلوى من بعض الأذواق في هديتنا - المباريات التي كان من المفترض أن تحد من هذا الطعم على اليسار وعلى اليمين ستقف جنبًا إلى جنب. بالإضافة إلى ذلك ، نحصل على تسلسل يتكون من k الحلويات ومباريات n-1 ، لأنه لا يوجد سوى الأذواق ، والمباريات تفصل بينها. لاحظ الآن أنه من خلال موقع المباريات ، يمكننا استعادة المجموعة الأصلية. بعد ذلك ، ستكون الإجابة هي عدد طرق وضع تطابق n-1 في خلية n + k-1 دون مراعاة الترتيب الذي يساوي عدد مجموعات n + k-1 بواسطة n-1 ، الصيغة: $(n + k-1)! / k! / (n-1)!$ عدد توليفات n خلال k مع التكرار .

الآن سننظر في العديد من المشكلات المتعلقة بمتجانسة التوافق من أجل دمج المواد.

المهمة 1

هناك 20 شخصًا ، كم من الطرق موجودة لإقرانهم
الحل: خذ الشخص الأول ، كم عدد الطرق المتاحة لاختيار زوج له: $inline$ خذ الشخص الثاني ، كم عدد الطرق المتاحة لاختيار زوج له: $inline$ . الجواب: 19! = 654729075

المهمة 2

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

(10! / (10 - 1)! / 1!)^{2} + (10! / (10 - 2)! / 2!)^{2} + . . . + (10! / (10 - 10)! / 10!)^{2}

$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)! / 10!) ^ 2$ .
الطريقة 2: النظر في العديد من الرجال الذين في الشركة والعديد من الفتيات الذين ليسوا في شركتها. لهذه المجموعة ، يمكنك بالتأكيد استعادة الشركة ، وعدد الأشخاص فيها يساوي دائمًا 10 ، منذ ذلك الحين

k + (10 - k) = 10

$k + (10 - k) = 10$ ، ك - عدد الرجال في الشركة ،

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

$inline$ .

لذلك ، اكتشفنا النظرية ، والآن سوف نتعلم كيفية إنشاء كائنات اندماجي باستخدام مكتبة الثعبان القياسية.
سوف نعمل مع مكتبة itertools

from itertools import *

باستخدام وظيفة التباديل ، يمكنك إنشاء كل التباديل لكائن قابل للتكرار.

مثال 1

 for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba

بناءً على الدعوة الثانية ، نلاحظ أن العناصر نفسها في المواقف المختلفة تعتبر مختلفة.

مثال 2

 for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb

يختلف الموضع عن التقليب بحدود عدد الخلايا المتاحة

مثال 3

 for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb cc

مع تخطيطات التكرار ، يمكنك التكرار بسهولة على جميع السلاسل ذات الطول الثابت التي تتكون من أحرف معينة

مثال 4

 for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd

باستخدام مجموعات بدون تكرار ، يمكنك التكرار على كل مجموعات الحروف غير المتكررة من سلسلة أو صفيف أو أي كائن قابل للتكرار دون النظر إلى الترتيب

مثال 5

 for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd

والنتيجة تشبه مجموعات الاستدعاء ، ولكن يتم أيضًا إضافة مجموعات مع نفس العناصر إلى النتيجة.

المواد:
NV غورباتشوف "مجموعة من مشاكل الأولمبياد في الرياضيات"
وثائق بيثون باللغة الروسية

التوافقية في بيثون