Python: simplifying nested FOR loop?

Question

I am wondering if there is a way to simplify the nested loop below. The difficulty is that the iterator for each loop depends on things from the previous loops. Here is the code:

# Find the number of combinations summing to 200 using the given list of coin

coin=[200,100,50,20,10,5,2,1]

total=[200,0,0,0,0,0,0,0]
# total[j] is the remaining sum after using the first (j-1) types of coin
# as specified by i below

count=0
# count the number of combinations

for i in range(int(total[0]/coin[0])+1):
    total[1]=total[0]-i*coin[0]
    for i in range(int(total[1]/coin[1])+1):
      total[2]=total[1]-i*coin[1]
      for i in range(int(total[2]/coin[2])+1):
          total[3]=total[2]-i*coin[2]
          for i in range(int(total[3]/coin[3])+1):
              total[4]=total[3]-i*coin[3]
              for i in range(int(total[4]/coin[4])+1):
                  total[5]=total[4]-i*coin[4]
                  for i in range(int(total[5]/coin[5])+1):
                      total[6]=total[5]-i*coin[5]
                      for i in range(int(total[6]/coin[6])+1):
                          total[7]=total[6]-i*coin[6]
                          count+=1

print count

See also "Recursively find all coin combinations that produces a specified amount", "How to ask and answer homework questions?". — outis
– outis, Commented Jun 20, 2012 at 22:35
your problem should be getting a smarter algorithm, not simplifying the nested loops — xvatar
– xvatar, Commented Jun 20, 2012 at 22:40
@outis - well if it is homework, I'm a bit annoyed with myself, but there's some effort here, and I guess a constraints library might be a bit tricky anyway... — Jon Clements
– Jon Clements, Commented Jun 20, 2012 at 22:40
it's 31 from project euler. Yes, if it asks for 2000 instead of 200, this is probably too slow, but I am just trying to translate my thoughts into a program. — user1470575
– user1470575, Commented Jun 21, 2012 at 11:13

Jon Clements · Accepted Answer · 2012-06-20 22:35:19Z

2

I recommend looking at http://labix.org/python-constraint which is a Python constraint library. One of its example files is actually permutations of coinage to reach a specific amount, and it all handles it for you once you specify the rules.

answered Jun 20, 2012 at 22:35

Jon Clements

143k34 gold badges254 silver badges288 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

jfs Over a year ago

coins.py

jfs Over a year ago

though it enumerates all solution that is less effective than just count them using e.g., dynamic programming

Jon Clements Over a year ago

I don't disagree - although I prefer generic solutions, then use other solutions if I experience bottleneck for a specific task

user1470575 Over a year ago

That's nice to know for more complicated problems, thank you.

8bitwide · Accepted Answer · 2012-06-20 23:43:51Z

1

You can get rid of all the int casting. An int/int is still an int in python ie integer division.

it looks like Recursion would clean this up nicly

count  = 0
coin=[200,100,50,20,10,5,2,1]
total=[200,0,0,0,0,0,0,0]

def func(i):
    global count,total,coin
    for x in range(total[i-1]/coin[i-1]+1):
        total[i]=total[i-1]-x*coin[i-1]
        if (i == 7):
            count += 1
        else:
            func(i+1)

func(1) print count

answered Jun 20, 2012 at 23:43

8bitwide

2,0811 gold badge17 silver badges24 bronze badges

2 Comments

John La Rooy Over a year ago

/ became floating division in Python3. It's better to use // if you want the int division as that works the same in Python2 and Python3

8bitwide Over a year ago

@gnibbler ahhh, go to know, I have avoided python 3 because I was annoyed at how much has changed. But at least now I can avoid sounding like an a** :-)

matzahboy · Accepted Answer · 2012-06-20 22:41:10Z

0

combinations = set()
for i in range(len(coins)):
  combinations = combinations | set(for x in itertools.combinations(coins, i) if sum(x) == 200)
print len(combinations)

It's a little slow, but it should work.

answered Jun 20, 2012 at 22:41

matzahboy

3,0341 gold badge22 silver badges25 bronze badges

Collectives™ on Stack Overflow

Python: simplifying nested FOR loop?

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related