यह मेरा कोड। सिक्के बदलने का कार्य। मुझे एक्सचेंज विकल्पों के साथ सूचियों की एक सूची प्राप्त करने की आवश्यकता है।

a = []
def coinChange(coins, amount, result=None):
    if result is None: 
        result = []
    
    if amount < 1 and sum(result) == 3:
        return a.append(result)

    else:
        for i in coins:
            if amount - i >= 0:
                result.append(i)
                coinChange(coins, amount - i, result)            
    return 

coinChange([1,2,3], 3)
print(a)

वो लौट आए

[1,1,1,2,2,1,3]

लेकिन मुझे सूचियों की एक सूची प्राप्त करने की आवश्यकता है। प्रत्येक उपन्यास में केवल वे संख्याएँ होनी चाहिए जो 3 तक जुड़ती हैं।

उदाहरण के लिए:

[[1,1,1], [2,1], [3]]

मुझे ऐसी सूची कैसे मिलेगी? धन्यवाद

0
Harry 13 सितंबर 2020, 17:24

2 जवाब

सबसे बढ़िया उत्तर

सरल उपाय

कोड

def coinChange(coins, amount, result=None, solutions = None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if solutions is None:
        solutions = []

    if amount == 0:
        # Add solution
        solutions.append(result[:])  # append a copy since result will change
    elif amount > 0:
        for i in coins:
            if amount - i >= 0:
                # Adding i to list of coins to try
                coinChange(coins, amount - i, result + [i,], solutions)
                
    return solutions
            

परीक्षण

a = coinChange([1,2,3], 3)
print(a)
            
# Capture the solution in a (i.e. don't make it global--generally bad practice)         
a = coinChange([1,2,3], 3)
print(a)

आउटपुट

[[1, 1, 1], [1, 2], [2, 1], [3]]

जेनरेटर का उपयोग करना और भी आसान

def coinChange(coins, amount, result=None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if amount == 0:
        # report solution
        yield result
        
    if amount > 0:
        for i in coins:
            yield from coinChange(coins, amount - i, result + [i,])    
            
a = list(coinChange([1,2,3], 3))
print(a)

कैश का उपयोग करना

GalSuchetzky उत्तर को संशोधित करके कैश के उपयोग को स्पष्ट करना सबसे आसान है।

समस्या

  • कॉइनचेंज फंक्शन पर सीधे कैश का उपयोग नहीं कर सकते क्योंकि तर्क हैशेबल नहीं हैं (जैसे सिक्के एक सूची है, इसलिए हैशेबल नहीं)
  • हम इसे नेस्टेड फ़ंक्शन (हेल्पर) का उपयोग करके वापस प्राप्त करते हैं, जिनके तर्क हैशबल हैं जो आवश्यकतानुसार सिक्कों में अनुक्रमित होते हैं

कोड

def coinChange(coins, sum_):
    '''
        Inputs:
            coins - list of coins
            sum_  - value coin should sum to (use sum_ since sum is a builtin function)
    '''
    
    def coinChangeHelper(j, total):
        '''
            Uses cache to compute solutions
            
            Need helper function since coins is a list so can't be hashed to placed in cache
            
            Inputs:
                j     - current index into coins
                total - current sum
        '''
        if (j, total) in mem_cache:
            # Use cache value
            return mem_cache[(j, total)]
        
        # Stop condition.
        if total == 0:
            mem_cache[(j, total)] = [[]]
        else:
            # Recursive step
            solutions = []

            for i in range(j, len(coins)):
                if coins[i] <= total:
                    lst = coinChangeHelper(i, total - coins[i])
                    solutions.extend([[coins[i]] + l for l in lst])

            mem_cache[(j, total)] = solutions
        
        return mem_cache[(j, total)]

    # Init cache
    mem_cache = {}
    
    return coinChangeHelper(0, sum_)

print(coinChange([1, 2, 3], 3))
1
DarrylG 13 सितंबर 2020, 23:48

मैं DarrylG's के उत्तर को और आगे ले जाऊंगा और रिकर्सन स्टैक के माध्यम से परिणामों को पारित करने के खिलाफ सलाह दूंगा, क्योंकि यह रिकर्सन के पूरे विचार को जटिल बनाता है।

सीधे शब्दों में कहें, तो आपको आमतौर पर चाहिए:

  1. मान लें कि आप अपनी समस्या का एक छोटा संस्करण हल कर सकते हैं (जो सटीक कार्य है जिसे आप कार्यान्वित कर रहे हैं)
  2. छोटी समस्याओं के समाधान का उपयोग करके मूल समस्या को हल करें (पुनरावर्ती चरण, यहां आप फ़ंक्शन को कॉल करते हैं)
  3. आपकी समस्या के लिए आपके पास सबसे सरल मामले के लिए एक स्पष्ट समाधान परिभाषित करें, जो अनिवार्य रूप से रिकर्सन की रोकथाम की स्थिति है।

इन युक्तियों के साथ समस्या को हल करने के लिए यहां एक उदाहरण कोड दिया गया है:

def coinChange(coins, sum):
    # Stop condition.
    if sum == 0:
        return [[]]

    # Recursive step
    solutions = []
    for i, coin in enumerate(coins):
        if coin <= sum:
            lst = coinChange(coins[i:], sum - coin)
            solutions.extend([[coin] + l for l in lst])

    return solutions


print(coinChange([1, 2, 3], 3))

चलने का परिणाम:

[[1, 1, 1], [1, 2], [3]]

यह जांचने के लिए अच्छा परीक्षण है कि आपने निर्भरता के बिना इन चरणों को किया है या नहीं, आपके कोड को एक-पंक्ति करने का प्रयास कर रहा है:

def coinChange(coins, sum):
    return [[c] + l for i, c in enumerate(coins) if c <= sum for l in coinChange(coins[i:], sum - c)] if sum > 0 else [[]]

ध्यान दें कि कभी-कभी यह अपठनीय हो सकता है, इसलिए इसे एक-पंक्ति के रूप में रखना आपके निर्णय का मौसम है।

1
GalSuchetzky 13 सितंबर 2020, 18:34