कल्पना कीजिए कि हमारे पास शेयरों की एक सूची है:

stocks = ['AAPL','GOOGL','IBM']

विशिष्ट स्टॉक कोई फर्क नहीं पड़ता, क्या मायने रखता है कि हमारे पास इस सूची में n आइटम हैं।

कल्पना कीजिए कि हमारे पास वजन की एक सूची है, 0% से 100% तक:

weights = list(range(101))

एन = 3 (या कोई अन्य संख्या) को देखते हुए मुझे वजन के हर संभावित संयोजन के साथ एक मैट्रिक्स तैयार करने की आवश्यकता है जो पूर्ण 100% तक हो। उदा.

0%, 0%, 100%
1%, 0%, 99%
0%, 1%, 99%
etc...

क्या itertools की कोई विधि है जो ऐसा कर सकती है? सुन्न में कुछ? ऐसा करने का सबसे कारगर तरीका क्या है?

3
Josh Pause 29 जुलाई 2018, 23:20
1
क्या आपको वाकई इस मैट्रिक्स की ज़रूरत है? यदि मेरा बैक-ऑफ-द-लिफाफा गणित सही है, तो एन = 3, 4 एम के लिए एन = 4 के लिए लगभग 30 के मान हैं, और यह वहां से ऊपर जा रहा है। आप उन सभी मूल्यों के साथ क्या करने जा रहे हैं? क्या आप सुनिश्चित हैं कि आपको केवल आवश्यकता नहीं है, उदाहरण के लिए, उनके बीच अच्छी तरह से वितरित 1000 संभावित मूल्यों को उत्पन्न करने का एक तरीका ताकि आप किसी प्रकार का ग्राफ खींच सकें?
 – 
abarnert
30 जुलाई 2018, 00:04
क्या weights हमेशा सूची [0, 1, 2, ..., 100] है?
 – 
Warren Weckesser
30 जुलाई 2018, 01:03

4 जवाब

इसे अनुकूलित करने का तरीका क्रमपरिवर्तन उत्पन्न करने का तेज़ तरीका नहीं है, यह यथासंभव कुछ क्रमपरिवर्तन उत्पन्न करना है।


सबसे पहले, आप यह कैसे करेंगे यदि आप केवल उस संयोजन को चाहते हैं जो क्रमबद्ध क्रम में था?

आपको 0 से 100 के सभी संभावित संयोजन उत्पन्न करने और फिर उसे फ़िल्टर करने की आवश्यकता नहीं है। पहली संख्या, a, 0 से 100 तक कहीं भी हो सकती है। दूसरी संख्या, b, 0 से (100-a) तक कहीं भी हो सकती है। तीसरी संख्या, c, केवल 100-ए-बी हो सकती है। इसलिए:

for a in range(0, 101):
    for b in range(0, 101-a):
        c = 100-a-b
        yield a, b, c

अब, 100*100*100 संयोजन उत्पन्न करने के बजाय उन्हें 100*50*1+1 तक फ़िल्टर करने के लिए, हम केवल 2000x स्पीडअप के लिए 100*50*1+1 उत्पन्न कर रहे हैं।

हालांकि, ध्यान रखें कि अभी भी लगभग X * (X/2)**N उत्तर हैं। इसलिए, X**N के बजाय X * (X/2)**N समय में उनकी गणना करना इष्टतम हो सकता है-लेकिन यह अभी भी घातीय समय है। और उसके आसपास कोई रास्ता नहीं है; आप परिणाम की एक घातीय संख्या चाहते हैं, आखिरकार।

आप itertools.product के साथ reduce या accumulate के साथ पहले भाग को अधिक संक्षिप्त बनाने के तरीकों की तलाश कर सकते हैं, लेकिन मुझे लगता है कि यह कम पढ़ने योग्य होगा, और आप सक्षम होना चाहते हैं किसी भी मनमाना N का विस्तार करें, और सभी क्रमपरिवर्तन प्राप्त करने के लिए न कि केवल क्रमबद्ध किए गए। इसलिए इसे तब तक समझने योग्य रखें जब तक आप ऐसा न कर लें, और फिर काम पूरा करने के बाद इसे संघनित करने के तरीकों की तलाश करें।


आपको स्पष्ट रूप से या तो एन चरणों से गुजरना होगा। मुझे लगता है कि लूप की तुलना में रिकर्सन के साथ समझना आसान है।

जब n 1 होता है, तो एकमात्र संयोजन (x,) होता है।

अन्यथा, प्रत्येक मान के लिए 0 से x तक, आपके पास वह मान हो सकता है, साथ में n-1 संख्याओं के सभी संयोजनों के साथ जो x-a के योग हैं। इसलिए:

def sum_to_x(x, n):
    if n == 1:
        yield (x,)
        return
    for a in range(x+1):
        for result in sum_to_x(x-a, n-1):
            yield (a, *result)

अब आपको केवल क्रमपरिवर्तन जोड़ने की आवश्यकता है, और आपका काम हो गया:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from itertools.permutations(combi)

लेकिन एक समस्या है: permutations स्थितियों की अनुमति देता है, मानों को नहीं। तो यदि आपके पास, (100, 0, 0), हैं, तो उसके छह क्रमपरिवर्तन हैं (100, 0, 0), (100, 0, 0), (0, 100, 0), (0, 0, 100), (0, 100, 0), (0, 0, 100).


यदि N बहुत छोटा है—जैसा कि आपके उदाहरण में है, N=3 और X=100 के साथ—यह प्रत्येक संयोजन के सभी 6 क्रमपरिवर्तनों को उत्पन्न करने और उन्हें फ़िल्टर करने के लिए ठीक हो सकता है:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from set(itertools.permutations(combi))

... लेकिन अगर एन बड़ा हो सकता है, तो हम वहां बहुत सारे व्यर्थ काम के बारे में भी बात कर रहे हैं।

बार-बार मूल्यों के बिना क्रमपरिवर्तन कैसे करें, इस पर बहुत सारे अच्छे उत्तर हैं। उदाहरण के लिए, यह प्रश्न देखें। उस उत्तर से कार्यान्वयन उधार लेना:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from unique_permutations(combi)

या, अगर हम SymPy या more-itertools:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from sympy.multiset_permutations(combi)

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from more_itertools.distinct_permutations(combi)
5
abarnert 30 जुलाई 2018, 00:00
उत्कृष्ट उत्तर, बहुत स्पष्ट। समय देने के लिए धन्यवाद।
 – 
Josh Pause
31 जुलाई 2018, 01:34
मुझे लगता है कि आपका perm_sum_to_x अनावश्यक है। sum_to_x फ़ंक्शन पहले से सभी वांछित क्रमपरिवर्तन उत्पन्न करता है (न कि केवल क्रमबद्ध क्रम में) ठीक एक बार। उदाहरण के लिए, list(sum_to_x(2, 3)) [(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)] देता है। तो perm_sum_to_x मौजूदा क्रमपरिवर्तन के अनावश्यक दोहराव जोड़ता है।
 – 
Mark Dickinson
1 सितंबर 2018, 20:02

आप जो खोज रहे हैं वह product itertools मॉड्यूल से है आप इसे नीचे दिखाए अनुसार उपयोग कर सकते हैं

from itertools import product

weights = list(range(101))
n = 3
lst_of_weights = [i for i in product(weights,repeat=n) if sum(i)==100]
0
InAFlash 29 जुलाई 2018, 23:39
ओपी ने सबसे कुशल तरीका पूछा। यह केवल कुछ हज़ार सही मूल्यों को उत्पन्न करने के लिए लाखों मूल्यों की गणना करेगा, जो शायद ही सबसे कुशल है।
 – 
abarnert
29 जुलाई 2018, 23:44
@abarnert, मुझे आपका जवाब पसंद है, लेकिन ओपी ने यह भी उल्लेख किया है "क्या इटर्टूल की कोई विधि है जो ऐसा कर सकती है"। तो, मेरा जवाब उसी ओर इशारा करता है
 – 
InAFlash
30 जुलाई 2018, 00:06

आपको जो चाहिए वह है combinations_with_replacement क्योंकि आपने अपने प्रश्न में लिखा था 0, 0, 100 जिसका अर्थ है कि आप दोहराव की अपेक्षा करते हैं, जैसे 20, 20, 60< /मजबूत> आदि

from itertools import combinations_with_replacement
weights = range(11)
n = 3
list = [i for i in combinations_with_replacement(weights, n) if sum(i) == 10]
print (list)

उपरोक्त कोड का परिणाम है [(0, 0, 10), (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6), (0, 5, 5), (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 2, 6), (2, 3, 5), (2, 4, 4), (3, 3, 4)]

range(10), n और sum(i) == 10 को अपनी जरूरत के अनुसार बदलें।

0
Sheldore 29 जुलाई 2018, 23:40
यह सभी उत्तरों को उत्पन्न नहीं करता है, क्योंकि ओपी (0, 1, 99) और (1, 0, 99) जैसे क्रमपरिवर्तन चाहता है। और यह उतना ही अक्षम है जितना कि InAFlash's answer—यह उन्हें 14 पर फ़िल्टर करने के लिए 1000 संयोजन उत्पन्न कर रहा है; एक्स या एन बढ़ने पर यह और भी खराब हो जाता है; ओपी की उदाहरण समस्या के लिए यह पहले से ही 1000000 संयोजन है।
 – 
abarnert
29 जुलाई 2018, 23:46

यह एक क्लासिक Stars and bar समस्या है, और Python की itertools मॉड्यूल वास्तव में एक ऐसा समाधान प्रदान करता है जो बिना किसी अतिरिक्त फ़िल्टरिंग के सरल और कुशल दोनों है। .

पहले कुछ स्पष्टीकरण: आप सभी संभावित तरीकों से 3 शेयरों के बीच 100 "अंक" विभाजित करना चाहते हैं। उदाहरण के लिए, आइए 100 के बजाय 10 अंक कम करें, जिसमें प्रत्येक का मूल्य 1% के बजाय 10% है। उन बिंदुओं को दस * वर्णों की एक स्ट्रिंग के रूप में लिखने की कल्पना करें:

**********

ये "सितारों और सलाखों" के "सितारे" हैं। अब दस तारों को 3 शेयरों में विभाजित करने के लिए, हम दो | विभाजक वर्ण ("स्टार और बार" के "बार") सम्मिलित करते हैं। उदाहरण के लिए, ऐसा एक विभाजन इस तरह दिख सकता है ::

**|*******|*

सितारों और सलाखों का यह विशेष संयोजन 20% AAPL, 70% GOOGL, 10% IBM के विभाजन के अनुरूप होगा। एक और विभाजन ऐसा दिख सकता है:

******||****

जो 60% AAPL, 0% GOOGL, 40% IBM के अनुरूप होगा।

अपने आप को यह विश्वास दिलाना आसान है कि दस * वर्णों और दो | वर्णों वाली प्रत्येक स्ट्रिंग तीन शेयरों के बीच दस बिंदुओं के ठीक एक संभावित विभाजन से मेल खाती है।

तो आपकी समस्या को हल करने के लिए, हमें केवल दस * स्टार कैरेक्टर और दो | बार कैरेक्टर वाले सभी संभावित स्ट्रिंग्स जेनरेट करने की जरूरत है। या, इसे दूसरे तरीके से सोचने के लिए, हम उन सभी संभावित युग्मों को खोजना चाहते हैं जिन्हें हम दो बार वर्णों को कुल लंबाई बारह की एक स्ट्रिंग में रख सकते हैं। पायथन के itertools.combinations फंक्शन को देने के लिए इस्तेमाल किया जा सकता है हमें वे संभावित स्थितियाँ, (उदाहरण के लिए itertools.combinations(range(12), 2) के साथ) और फिर प्रत्येक जोड़ी की स्थिति को range(10) के विभाजन में तीन टुकड़ों में अनुवाद करना आसान है: शुरुआत और अंत में एक अतिरिक्त काल्पनिक विभक्त वर्ण डालें स्ट्रिंग के, फिर विभाजक के प्रत्येक जोड़े के बीच सितारों की संख्या पाएं। तारों की वह संख्या दो विभाजकों के बीच की दूरी से बस एक कम है।

यहाँ कोड है:

import itertools

def all_partitions(n, k):
    """                                                                         
    Generate all partitions of range(n) into k pieces.                          
    """
    for c in itertools.combinations(range(n+k-1), k-1):
        yield tuple(y-x-1 for x, y in zip((-1,) + c, c + (n+k-1,)))

प्रश्न में दिए गए मामले के लिए, आप all_partitions(100, 3) चाहते हैं। लेकिन यह 5151 विभाजन देता है, (0, 0, 100) से शुरू होकर (100, 0, 0) पर समाप्त होता है, इसलिए यहां परिणाम दिखाना अव्यावहारिक है। इसके बजाय, यहां एक छोटे मामले में परिणाम दिए गए हैं:

>>> for partition in all_partitions(5, 3):
...     print(partition)
... 
(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 0, 4)
(1, 1, 3)
(1, 2, 2)
(1, 3, 1)
(1, 4, 0)
(2, 0, 3)
(2, 1, 2)
(2, 2, 1)
(2, 3, 0)
(3, 0, 2)
(3, 1, 1)
(3, 2, 0)
(4, 0, 1)
(4, 1, 0)
(5, 0, 0)
0
Mark Dickinson 1 सितंबर 2018, 20:38