Need help translating this python code - Computer Technical Help

Two Plus Two Forums Other Topics Computer and Technical Help

Need help translating this python code

Post Reply Subscribe

...

04-13-2013 , 11:29 PM

Addict_x

newbie

Join Date: Mar 2007 Posts: 43

I am working on a similar homework project in c++ and would like to know how this python function works. Could someone translate or comment the code for me? This is a program that finds all combinations of coins given a dollar value. I have been able to recursively get the number of solutions but am having a hard time printing out the combinations... thanks!

Code:

#!/usr/bin/python

# find the number of ways to reach a total with the given number of combinations

cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
            comb.append( (left, denominations[i]) )
            i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print " ".join("%d %s" % (n,names[c]) for (n,c) in comb)
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

print count_combs(cents, 0, [], None)

Quote

04-14-2013 , 12:09 PM

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

Well, the good news is that part of the reason you're confused is because of some...questionable...stylistic choices in that code. For instance, "denominations" and "names" are global variables here and "cents" is not.

Since I couldn't figure out what a lot of the variables did at first: "i" is the current coin in use; it starts at 0 because "25" is the leftmost coin. "left" means "remaining" in this context, not the antonym of "right".

I'm 99% sure the "add" variable is both unnecessary and poorly named. It looks like what it's doing is passing the most recent decision as an argument along with a list of combinations so far, then appending the most recent decision in the next function call. But you could do the same thing by changing the recursive call to:

Code:

count_combs(left-x*cur, i+1, comb[:]+[(x,cur)])

The conditionals in the middle are kind of goofy; for instance, you could cut down on the confusing "ifs" if you just assume the last denomination is always 1. If you don't make that assumption, the code is actually wrong. So a more sensible version might be:

Code:

if left == 0 or (i+1) == denominations:
    if left:
        comb.append((left,1))
    else:
        comb.extend((0, denominations[k]) for k in range(i, len(denominations))

Speaking of which, if you're going to try to translate this to C, you need to understand that Python has what are called "comprehensions" which are sort of a simplified for loop for short expressions. In the case of the author's sum, here's a C-like pseudocode equivalent of that return line:

Code:

total = 0
cur = demonations[i] //aka "the biggest coin we're permuting against
for (x = 0; x < left/cur+1; ++x)
{
    total += count_combs(left-x*cur, i+1, copy_of_answer_so_far_since_these_variable_names_are_cryptic)
}
return total

Last edited by Xhad; 04-14-2013 at 12:22 PM.

Quote

04-14-2013 , 12:14 PM

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

The Python code in the OP looks like it was written by someone who is not a Python programmer (I'd guess by a C programmer)

Quote

04-14-2013 , 12:23 PM

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

clowntable, now I'm all curious what yours would look like. I'm gonna go dig up the similar one I made for a Project Euler problem like a year ago and see if it embarrasses me yet.

Quote

04-14-2013 , 01:16 PM

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

Mine would obviously look like this:

Code:

:- use_module(library(clpfd)).

solve_coins(Cents, Coins) :-
  Coins = [Quarters, Dimes, Nickels, Pennies],
  domain(Coins, 0, Cents),
  Cents #= 25*Quarters + 10*Dimes + 5*Nickels + Pennies,
  labeling([], Coins).

count_solutions(Cents, Count):-
  findall(true, solve_coins(Cents,_), ListOfSolutions),
  length(ListOfSolutions, Count).

| ?- count_solutions(200, Count).
Count = 1463 ? ;
no
% zip,source_info

Right tool for the right job

Edit: Depending on how you interpret the question you might want to add a Cents #>0 constraint

Code:

Cents #= 25*Quarters + 10*Dimes + 5*Nickels + Pennies,
Cents #>0,

If the answer to "How many combinations of coins can you have for 0 cents" should be 1 (i.e. the solution is 0,0,0,0) then leave it out if that's too twisted add it. I think it makes sense that the solution is actually 1 to differentiate it from arranging the coins to get -1 cents which has no solution.

Last edited by clowntable; 04-14-2013 at 01:38 PM.

Quote

04-14-2013 , 02:50 PM

Addict_x

newbie

Join Date: Mar 2007 Posts: 43

Thanks for taking the time you two! That helps clear things up. As an aside, I have to stop looking at other people's code when I'm having a hard time coming up with a solution to a problem. Here, under the constraints of the assignment and the recursion to solve this problem at the limit of my intelligence I've had a hard time. I probably should have just begun by asking advice on my algorithm from the get go. Which I may yet do...

Quote

04-14-2013 , 03:43 PM

ballin4life

veteran

Join Date: Jun 2006 Posts: 2,121

Quote:

Originally Posted by Addict_x

Reading other people's code is a pretty important skill though IMO. Most programmers have to read someone else's code very frequently.

(BTW I find the code in the OP pretty hard to read too).

I think this would work for the problem btw:

Code:

def count_combs(amount, denoms):
  if amount == 0: return 1
  if amount < 0: return 0
  return sum( [count_combs(amount-x, [y for y in denoms if y<=x]) for x in denoms] )

with the list comprehensions unrolled it would look like this

Code:

def count_combs(amount, denoms):
  if amount == 0: return 1
  if amount < 0: return 0
  combinations = 0
  for x in denoms:
    # next part is just getting the list of denoms that are <= x
    smaller_denoms = []
    for y in denoms:
      if y <= x:
        smaller_denoms.append(y)
    
    # recursive call, and sum
    combinations += count_combs(amount-x, smaller_denoms)
  
  return combinations

Quote

04-15-2013 , 03:03 AM

spiral

grinder

Join Date: Jan 2003 Posts: 528

Quote:

Originally Posted by ballin4life

I think this would work for the problem btw:

Code:

def count_combs(amount, denoms):
  if amount == 0: return 1
  if amount < 0: return 0
  return sum( [count_combs(amount-x, [y for y in denoms if y<=x]) for x in denoms] )

This is i think pretty clear, but kind of horrible python (which I suspect you know)

I basically never use recursion in production python unless I know what the depth is going to be like. I realize this is an exercise and you know this. Just wanted to mention for others:

- python doesn't have tail call optimization
- default max recursion depth varies by platform for cpython (last I checked)
- its pretty slow
- the version above is very recursive even for a recursive solution (trades off to get brevity, could reduce depth a fair bit just using divmod)

I didn't bother to calculate the exact limits, but some quick testing:

on my mac the snippet above with denoms = [25, 10, 5, 1] on cpython will hit max recursion depth even with amount = 999! (works but very very slow with amount = 980)

The bottom line is I love python but don't do stuff like this in languages without tail call optimization.

Quote

04-15-2013 , 05:51 AM

ballin4life

veteran

Join Date: Jun 2006 Posts: 2,121

Quote:

Originally Posted by spiral

Bottom up implementation is ugly

Code:

def count_combs(amount, denoms):
  # 2D array of all 1s to start
  combs = [ ([1]*(amount + 1))[:] for x in range(len(denoms)) ]
  for max_coin_index in range(len(denoms)):
    for amt in range(1,amount+1):
      combs[max_coin_index][amt] =  sum( [combs[index][amt-denoms[index]] for index in range(max_coin_index+1) if denoms[index] <= amt])
  
  return combs[-1][amount]

Near instant though even if amount = 100000

This variation on the recursive version is faster, but still hits max recursion depth (for me) around amount=1500

Code:

def count_combs(amount, denoms, cache={}):
  if amount == 0: return 1
  if amount < 0: return 0
  try:
    return cache[ (amount, tuple(denoms)) ]
  except KeyError:
    cache[ (amount, tuple(denoms)) ] = sum( [count_combs(amount-x, [y for y in denoms if y<=x], cache) for x in denoms] )
    return cache[ (amount, tuple(denoms)) ]

if I unroll the sum it can get up to amount = 2500 or so

Last edited by ballin4life; 04-15-2013 at 06:09 AM.

Quote

04-15-2013 , 07:57 AM

#10

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

Weird, I dug up my PE version where I did almost the same thing and mine handles N = 10000 in about ten seconds with no issues. Around 45 seconds if I use the original denomination list from the problem (200, 100, 50, 20, 10, 5, 2, 1)

Code:

def mcountToN(i, N, denoms, runningtotal=0, cache={}):
    if i >= len(denoms):
        return 0
    
    count = 0
    total = runningtotal
    while total < N:
        if (i, total) not in cache:
            cache[(i, total)] = mcountToN(i+1, N, denoms, total)
        count += cache[(i, total)]
        total += denoms[i]
    return (total == N) + count

Quote

04-15-2013 , 09:17 PM

#11

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Does the solution have to be so expensive? It seems to make sense to do something different.

Suppose, we are trying to find how many coins we can make 25 cents with. The idea I have is to always compute the minimum amounts of coins at each case. So the minimum count you need for 25 cents is one 25 cent coin:

[25]

Then compute the minimum coins you need to get the v[0] value:
[10, 10, 5]

Then repeat:
[5, 5, 10, 5]

The repeat:
[1, 1, 1, 1, 1, 5, 10, 5]

We see there are ones, so go to five:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10, 5]

Then:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5, 5]

And each step through this process is one more count. When you are at all ones, you are done.

I guess the alternative would be:

[25]

[10, 10, 5]

[5, 5, 10, 5]

[5, 5, 5, 5, 5]

[1, 1, 1, 1, 1, 5, 5, 5, 5]

....

I like the first one better because you can actually destroy the first part of the list and keep dissolving down until you have an empty list, so mixing in that strategy:

[25] ; sum = 25

[10, 10, 5]; sum = 25

[5, 5, 10, 5]; sum = 25

[1, 1, 1, 1, 1, 5, 10, 5]; destroy the ones;

[5, 10, 5]; sum = 20

[1, 1, 1, 1, 1, 10, 5]; destroy the ones:

[10, 5]; sum = 15

...

Better, worse than looping around?

Quote

04-15-2013 , 09:53 PM

#12

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

Dave, one immediate problem I see is that I'm not sure you guard against duplicates (this type of problem tends to count [5,10] and [10,5] as the same thing)

Consider N=30. [30] can be [25,5] or [10,10,10], so you have to count both. Can you justify breaking down one but not the other? If you can't, you're going to get some duplicates further down the line such as, for instance, [10, 10, 5, 5] is easily reachable from both of the above. I suppose you could keep a set of known combinations and stop breaking down any combination that already exists in the set, but at that point I'm not convinced there's any speed gain over the memoized brute force solution.

Quote

04-15-2013 , 10:37 PM

#13

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

The algorithm guards against duplicates by always working with the head of the list which keeps all permutations unique.

This is probably a better visualization of what I am suggesting:

[25]
[[10], 10, 5]
[[5, 5], 10, 5]
[[[1, 1, 1, 1, 1], 5], 10, 5]
;; destroy the ones
[[5], 10, 5]
[[1, 1, 1, 1, 1], 10, 5]

Obviously that much list manipulation isn't needed, though I guess it could be a decent approach to adding in memoization.

I don't have an answer for the 30c issue though.

I'll look up something this evening. I think there is something more mathy that can be used, but I'm not sure.

Quote

04-16-2013 , 10:02 PM

#14

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Did some playing around and discovered a few interesting things. The first interesting thing is this:

Code:

mainList = []
subList = []

for i in range(200):
    subList.append(count_combs(i, denoms))
    if len(subList) == 5:
      mainList.append(subList)
      subList = []

print(mainList)

which (cleaned up):

Code:

>>> 
[[1, 1, 1, 1, 1], 
 [2, 2, 2, 2, 2], 
 [4, 4, 4, 4, 4], 
 [6, 6, 6, 6, 6], 
 [9, 9, 9, 9, 9], 
 [13, 13, 13, 13, 13], 
 [18, 18, 18, 18, 18], 
 [24, 24, 24, 24, 24], 
 [31, 31, 31, 31, 31], 
 [39, 39, 39, 39, 39], 
 [49, 49, 49, 49, 49], 
 [60, 60, 60, 60, 60], 
 [73, 73, 73, 73, 73], 
 [87, 87, 87, 87, 87], 
 [103, 103, 103, 103, 103], 
 [121, 121, 121, 121, 121], 
 [141, 141, 141, 141, 141], 
 [163, 163, 163, 163, 163], 
 [187, 187, 187, 187, 187], 
 [213, 213, 213, 213, 213], 
 [242, 242, 242, 242, 242], 
 [273, 273, 273, 273, 273], 
 [307, 307, 307, 307, 307], 
 [343, 343, 343, 343, 343], 
 [382, 382, 382, 382, 382], 
 [424, 424, 424, 424, 424], 
 [469, 469, 469, 469, 469], 
 [517, 517, 517, 517, 517], 
 [568, 568, 568, 568, 568], 
 [622, 622, 622, 622, 622], 
 [680, 680, 680, 680, 680], 
 [741, 741, 741, 741, 741], 
 [806, 806, 806, 806, 806], 
 [874, 874, 874, 874, 874], 
 [946, 946, 946, 946, 946], 
 [1022, 1022, 1022, 1022, 1022], 
 [1102, 1102, 1102, 1102, 1102], 
 [1186, 1186, 1186, 1186, 1186], 
 [1274, 1274, 1274, 1274, 1274], 
 [1366, 1366, 1366, 1366, 1366]]
>>>

Notice a pattern? Logically, there is only 1 way to make 4 cents, and there are two ways to make 5 cents. There would be 2 ways to make 6 cents since those pennies don't matter. With this intuition, I guess you'd only need to track the (mod 5) numbers.

So, since there is a pattern, there must be some math wizardry. Turns out there are two interesting things here. The first is using combinatrics, which I know nothing about, but I can at least give the equation:

Quote:

Expansion of 1/((1-x)^2*(1-x^2)*(1-x^5)).

The fascinating part is that this is the expansion for finding the combinations of 1, 2, and 5 cents, which maps to [1, 5, 10, 25].

src = http://oeis.org/A001304

I was thinking along something like this. I figured there was some way to use GCD to minimize the work here but this is one gap in my knowledge.

This next one will blow your brain, but unfortunately, I don't know how to do this stuff either.

Quote:

The Bijection Rule acts as a magnifier of counting ability; if you figure out the size of one set, then you can immediately determine the sizes of many other sets via bijections.

A = all ways to select a dozen donuts when five varieties are available
B = all 16-bit sequences with exactly 4 ones
An example of an element of set
A
is:

Code:

0 0                     0 0 0 0 0 0     0 0     00
chocolate  lemon-filled   sugar         glazed  plain

0
and left a gap between the different varieties. Thus, the selection above contains two chocolate donuts, no lemon-filled, six sugar, two glazed, and two plain. Now let’s put a 1 into each of the four gaps:

Code:

00 1      1  000000  1 00 1 00

and close up the gaps:

0011000000100100

We’ve just formed a 16-bit number with exactly 4 ones —an element of B! This example suggests a bijection from set A to set B.

The resulting sequence always has 16 bits and exactly 4 ones, and thus is an
element of B. Moreover, the mapping is a bijection: every such bit sequence comes from exactly one order of a dozen donuts. Therefore,

Lemma 14.1.1.
The number of ways to select n donuts when k flavors are available is the same as the number of length-n binary sequences with k ones.

This example demonstrates the power of the bijection rule. We managed to prove that two very different sets are actually the same size —even though we don’t know exactly how big either one is. But as soon as we figure out the size of one set, we’ll immediately know the size of the other. This particular bijection might seem frighteningly ingenious if you’ve not seen
it before.

src = (page 500) http://courses.csail.mit.edu/6.042/spring12/mcs.pdf

So, basically, find all the GCDs and compute that set of numbers to find the expansion of the larger set via the bijection rule. Push around the bits to print all permutations if you really want to, and..?

Quote

Post Reply Subscribe

...