python - 找出所有可能的变化排列

Question

我有一个有趣的面试问题，但我很难解决(我有 10 个排列中的 7 个)

问题是

Find all possible permutations to make change given the following coins, 25¢, 10¢, 5¢. The answer MUST BE saved in a list, and MUST BE returned as a JSON string when the method is called

此外，要求是打印时，解决方案必须如下所示

For instance, given an amount of 50¢, the solution should look like the following when printed out

25: 2, 10: 0, 5: 0
25: 1, 10: 1, 5: 3
25: 1, 10: 2, 5: 1
25: 1, 10: 0, 5: 5
25: 0, 10: 5, 5: 0
25: 0, 10: 4, 5: 2
25: 0, 10: 3, 5: 4
25: 0, 10: 2, 5: 6
25: 0, 10: 1, 5: 8
25: 0, 10: 0, 5: 10

不用说，2个小时(考试时间限制)后我无法完成。但是，如果我能解决这个问题，它会让我徘徊。在过去的 6 个小时里我一直在尝试得到结果，但我能想到的最好的结果是

1 => {25: 2, 10: 0, 5: 0}
2 => {25: 1, 10: 1, 5: 3}
3 => {25: 1, 10: 2, 5: 1}
4 => {25: 1, 10: 0, 5: 5}
5 => {25: 0, 10: 5, 5: 0}
6 => {25: 0, 10: 1, 5: 8}
7 => {25: 0, 10: 0, 5: 10}

使用此代码

class ChangeMachine(object):
    def __init__(self, amount, coins=[25, 10, 5]):
        self.amount = amount
        self.coins = coins
        self.result = []

        self.initial_way = {}
        for coin in coins:
            self.initial_way[coin] = 0

    def getAllPermutations(self):
        for index in xrange(0, len(self.coins)):
            coin = self.coins[index]

            self.changeFromSameCoin(self.amount, coin)

            self.changeUsingOneCoin(self.amount, coin, self.coins[index + 1:])

    def changeFromSameCoin(self, amount, coin):
        """loops through all the coins, finding the ones which can be divided
        into the amount evenly

        Args:
            amount: int
            coin: int

        Returns:
            None
        """
        way = dict(self.initial_way)

        if amount % coin == 0:
            way[coin] = amount / coin
            self.result.append(dict(way))

    def changeUsingOneCoin(self, amount, initial_coin, coin_list):
        """Makes change using 1 large coin and the rest small coins
        Args:
            amount: int
            initial_coin: int - the "large" denomination that is to be used once
            coin_list: list - contains the remainder of the coins 
        """

        if amount <= initial_coin:
            return

        remainder   = amount - initial_coin
        init_way    = dict(self.initial_way)
        num_coins   = len(coin_list)
        coin_used   = 0

        outer_counter = 0

        # keep track of the number of times the outer coins are used
        # make it 1 because the outer coin has to be used at least once
        # even if outer coin is > remainder, we are still trying to use
        # it once
        outer_coin_used = 1

        # since the initial coin MUST BE used at least once, go ahead and
        # create an initial dictionary that has the initial coin used
        # once
        init_way[initial_coin] = 1

        while outer_counter < num_coins:
            outer_coin = coin_list[outer_counter]

            # initialize way on every loop
            way = dict(init_way)

            # subtract the current outer coin from the remainder. We do this
            # because if the remainder is 0, then it means that only 1 of this
            # coin and the initial coin are needed to make change
            # If the remainder is negative, then, one of the larger coin and
            # one of this coin, cannot make change
            # The final reason is because if we make change with the other
            # coins, we need to check if we double, triple, etc this coin
            # that we can still make change.
            # This helps us find all permutations
            remainder -= (outer_coin * outer_coin_used)

            if remainder < 0:
                # move to next coin using the outer_counter
                outer_counter += 1

                # reset the remainder to initial - large coin
                remainder = amount - initial_coin

                # rest the times the coin was used to 1
                outer_coin_used = 1
                continue

            way[outer_coin] += outer_coin_used

            if remainder == 0:
                # add the way we just found to our result list
                self.result.append(dict(way))

                # move to the next element in the list
                outer_counter += 1

                # reset the remainder, our way result set, and times the
                # outer coin was used
                remainder = amount - initial_coin
                way       = dict(init_way)
                outer_coin_used = 0

                continue

            # so, if we got here, the outer coin reduced the remainder, but
            # didn't get it to 0
            for index in range(outer_counter + 1, num_coins):
                # our goal here is to make change with as few of coins as
                # possible
                inner_coin = coin_list[index]

                if remainder % inner_coin == 0:
                    way[inner_coin] = remainder / inner_coin
                    remainder = 0
                    break

                if remainder - inner_coin < 0:
                    # this coin is too large, move onto the next coin
                    continue

                # this coin goes into the remainder some odd number of times
                # subtract it from our remainder and move onto the next coin
                remainder /= inner_coin
                way[inner_coin] += remainder

            # end for index in range()

            if remainder == 0:
                # we found a way to make change, save it
                self.result.append(dict(way))

            # reset the remainder to initial - large coin
            remainder = amount - initial_coin

            # increment the outer coin used by 1, because we will try
            # to decrement remainder by more than 1 outer coin
            outer_coin_used += 1

        # end while loop

        return
    # end def changeUsingOneCoin()
# end class

from pprint import pprint

def main(amount, coins=[25, 10, 5]):
    result = []

    amount = 50
    coins  = [25, 10, 5]
    cm = ChangeMachine(amount, coins)
    # cm.changeUsingOneCoin(amount, coins[0], coins[1:])

    cm.getAllPermutations()

    counter = 1
    for record in cm.result:
        print "{} => {}".format(counter, record)
        counter += 1

    return result

if __name__ == '__main__':

    """
    Result MUST BE a list of dictionaries containing all possible answers

    For Example: if main(50, [25, 10, 5]) should return

    [
        {25: 2},
        {25: 1, 10: 2, 5: 1},
        {25: 1, 10: 1, 5: 3},
        {25: 1, 10: 0, 5: 5},
        {25: 0, 10: 5, 5: 0},
        {25: 0, 10: 4, 5: 2},
        {25: 0, 10: 3, 5: 4},
        {25: 0, 10: 2, 5: 6},
        {25: 0, 10: 1, 5: 8},
        {25: 0, 10: 0, 5: 10},
    ]
    """
    result = main(50)

我知道我不会得到这份工作。但是，我真的很想知道解决方案

Answer 1

他们对实际输出有多严格(有些公司在这方面可能相当迂腐)？这是一个快速解决方案，仅使用几个嵌套循环即可生成 10 种组合:

from itertools import count
from pprint import pprint
from operator import itemgetter

results = []
target = 50

for q in count(0):
  for d in count(0):
    for n in count(0):
      if n * 5 + d * 10 + q * 25 == target:
        results.append({25: q, 10: d, 5: n})
      if n * 5 + d * 10 + q * 25 > target:
        break
    if d * 10 + q * 25 > target:
      break
  if q * 25 > target:
    break

results.sort(key = itemgetter(5))
results.sort(key = itemgetter(10), reverse = True)
results.sort(key = itemgetter(25), reverse = True)
pprint(results)

产品:

[{5: 0, 10: 0, 25: 2},
 {5: 1, 10: 2, 25: 1},
 {5: 3, 10: 1, 25: 1},
 {5: 5, 10: 0, 25: 1},
 {5: 0, 10: 5, 25: 0},
 {5: 2, 10: 4, 25: 0},
 {5: 4, 10: 3, 25: 0},
 {5: 6, 10: 2, 25: 0},
 {5: 8, 10: 1, 25: 0},
 {5: 10, 10: 0, 25: 0}]

sort 调用只是为了将列表按照它们提供的顺序排列(但这似乎很荒谬，恕我直言)。