पाइथन में संयोजक

2.2 संस्करण के साथ शुरू, मानक अजगर पुस्तकालय दहनशील वस्तुओं को बनाने के लिए कई उपकरण प्रदान करता है, लेकिन मुझे इंटरनेट पर एक भी लेख नहीं मिला जो उनके साथ काम करने के बारे में विस्तार से वर्णन करेगा। इसलिए, मैंने इस चूक को ठीक करने का फैसला किया।

इसके साथ शुरू करने के लिए, मैं कॉम्बिनेटरिक्स और इसके मूल सूत्रों के बारे में बात करूंगा। यदि आप पहले से ही गणित के इस भाग से परिचित हैं, तो आप इन अनुच्छेदों को छोड़ सकते हैं।

मान लीजिए कि हमारे पास n अलग-अलग अक्षरों से मिलकर एक स्ट्रिंग है और हम इन अक्षरों को फिर से व्यवस्थित करने के लिए सभी तरीकों की गणना करना चाहते हैं जैसे कि एक नई लाइन प्राप्त करना। लाइन में पहली स्थिति के लिए, हम अपने पास मौजूद n अक्षरों में से एक को चुन सकते हैं, दूसरी स्थिति के लिए n- 1 अक्षर और इतने पर। परिणामस्वरूप, हम उत्पाद n (n-1) प्राप्त करते हैं ... * 1 = n! पुनरावृत्ति के बिना n तत्वों के क्रमपरिवर्तन की संख्या ।

अब कल्पना करें कि एक स्ट्रिंग में अक्षरों की संख्या सीमित है। हमारे पास n अक्षर उपलब्ध हैं और हम उनसे लंबाई के स्ट्रिंग बनाने के तरीकों की संख्या की गणना करना चाहते हैं, जहां k <n, हम प्रत्येक अक्षर का उपयोग केवल एक बार कर सकते हैं। फिर हम पंक्ति में पहले स्थान पर n अक्षर में से एक, दूसरी स्थिति में n-1 अक्षरों में से एक और k-th स्थिति पर n-k + 1 अक्षरों में से एक डाल सकते हैं। पंक्तियों की कुल संख्या n (n - 1) (n - 2) के बराबर होगी ... (n - k + 2) (n - k + 1) = n! / (Nk)! n से k तक नियुक्तियों की संख्या । यदि अक्षरों की विशिष्टता की आवश्यकता नहीं होती है, तो हम सूत्र n ... n n = n ^ को दोहराव के साथ n से k तक प्लेसमेंट की संख्या प्राप्त करते हैं ।

इससे पहले, हम तत्वों के क्रम को ध्यान में रखते हुए अनुक्रमों के माध्यम से हल करते हैं, और अगर आदेश हमारे लिए कोई मायने नहीं रखता है। उदाहरण के लिए, हमारे पास अलग-अलग कैंडीज हैं और हम एक दोस्त को देने के लिए उनमें से k चुनना चाहते हैं, और k <n। आदेश के संबंध में n से k कैंडीज़ चुनने के कितने तरीके हैं? इसका उत्तर सरल है, शुरुआत में हम बिना किसी पुनरावृत्ति के n द्वारा k का स्थान प्राप्त करेंगे, लेकिन फिर उनके अनुक्रम के विभिन्न क्रम वाली मिठाइयों के एक ही सेट को दोहराया जाएगा। K कैंडीज को पुनर्व्यवस्थित करने के कितने तरीके हैं? यह सही है, पुनरावृत्ति के बिना कश्मीर तत्वों का एक क्रमचय। अंतिम उत्तर: k द्वारा n के प्लेसमेंट को पुनरावृत्ति के बिना k के क्रमपरिवर्तन द्वारा विभाजित किया गया है। सूत्र: $$$n! / (n-k)! / k $$n द्वारा k के संयोजन की संख्या ।

मामले को और अधिक जटिल मानें, हमारे पास n बॉक्स हैं, जिनमें से प्रत्येक में एक ही स्वाद के कई कैंडी हैं, लेकिन अलग-अलग बक्से में स्वाद अलग-अलग हैं। K कैंडीज से किसी दोस्त को उपहार देने के कितने तरीके हैं, और किसी भी संख्या में एक ही स्वाद हो सकता है? चूंकि ऑर्डर हमारे लिए कोई मायने नहीं रखता है, तो आइए उपहार की मिठाइयों की व्यवस्था इस प्रकार करें: शुरुआत में क्रमिक रूप से पहले स्वाद की कैंडीज, फिर दूसरे और इतने पर मिलेंगी, और हम अपने उपहार में किसी भी स्वाद की कैंडी नहीं होने पर विभिन्न स्वादों की कैंडी के बीच मैच डालेंगे। मैच जो इस स्वाद को बाईं ओर और दाईं ओर करने वाले थे, कंधे से कंधा मिलाकर खड़े होंगे। इसके अलावा, हम कश्मीर मिठाई और n-1 मैचों से मिलकर एक अनुक्रम प्राप्त करते हैं, क्योंकि केवल n स्वाद हैं, और मैच उन्हें अलग करते हैं। अब ध्यान दें कि मैचों के स्थान से, हम मूल सेट को पुनर्स्थापित कर सकते हैं। फिर उत्तर बिना किसी आदेश के ध्यान में रखते हुए n + k-1 सेल में n-1 मैच लगाने के तरीकों की संख्या होगी, जो n-1 द्वारा n + k-1 के संयोजन की संख्या के बराबर है, सूत्र: $$$(n + k-1)! / k! / (n-1)$पुनरावृत्तियों के साथ कश्मीर के माध्यम से n के संयोजन की संख्या ।

अब हम सामग्री को समेकित करने के लिए कॉम्बिनेटरिक्स पर कई समस्याओं पर विचार करेंगे।

टास्क 1

20 लोग हैं, उन्हें बाँधने के कितने तरीके हैं
समाधान: पहला व्यक्ति लें, उसके लिए एक जोड़ी चुनने के कितने तरीके हैं: $$$20-1 = 19$, दूसरा व्यक्ति लें, उसके लिए एक जोड़ी चुनने के कितने तरीके हैं: $$$20-2-1 = 17$। उत्तर: 19 !!! = 654729075 पर

टास्क २

10 पुरुष और 10 लड़कियाँ हैं, कितने ही तरीके हैं उन्हें तोड़ने के लिए कंपनियों में एक ही संख्या में पुरुषों और लड़कियों को मिलाकर एक खाली कंपनी नहीं मानी जाती
समाधान:
विधि 1: एक आदमी और एक लड़की से एक कंपनी को इकट्ठा करने के तरीकों की संख्या एक लड़की को चुनने के तरीकों की संख्या और एक आदमी को चुनने के तरीकों की संख्या के बराबर है। 10 में से एक लड़की को चुनने के तरीकों की संख्या पुनरावृत्ति के बिना 10 से 1 के संयोजन के बराबर है, यह पुरुषों के साथ समान है, इसलिए हम वर्ग होंगे। अगला, हम इसी तरह 10 से 2 के संयोजन की गणना करते हैं, 10 से 3 तक, और इसी तरह 10 से 10 के संयोजन पर। अंतिम सूत्र: $$$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)!) 10!) ^ 2$।
विधि 2: कई पुरुषों पर विचार करें जो कंपनी में हैं और कई लड़कियां जो उसकी कंपनी में नहीं हैं। इस सेट के लिए, आप निश्चित रूप से कंपनी को पुनर्स्थापित कर सकते हैं, और इसमें लोगों की संख्या हमेशा 10 के बराबर होती है, क्योंकि $$$k + (10 - k) = 10$, के - कंपनी में पुरुषों की संख्या, $$$10 - के$- इसमें लड़कियों की संख्या शामिल नहीं है। इस तरह के सेट की संख्या 20 से 10 के संयोजन की संख्या के बराबर है, अंतिम उत्तर में हम एक को भी घटाएंगे ताकि खाली कंपनी को ध्यान में न रखा जाए जब हमारे सेट में 10 लड़कियां हों। अंतिम सूत्र: $$$20! / (20-10)! / 10! - 1 = $ 18475$।

इसलिए, हमने सिद्धांत का पता लगाया, अब हम सीखेंगे कि मानक पायथन लाइब्रेरी का उपयोग करके कॉम्बिनेटरियल ऑब्जेक्ट कैसे उत्पन्न करें।
हम 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 गोर्बाचेव "गणित में ओलंपियाड समस्याओं का संग्रह"
रूसी में पायथन प्रलेखन