Python guru's

bardinjw · 06-22-2005, 11:36 AM

I was trying to demonstrate a short academic example called "Zen Archery"

pretty simple, find combinations of 5 in the list that add up to 200
here's the code i used: (the sort was just to make the output easier to see duplicates)

Code:

#########################
targets=[97,101,139,41,37,31,29,89,23,19,8,13,131,19,73,97,19,139,79,67,61,17,113,127]

targets.sort()
def combine(things, n):
    if n == 0: yield []
    else:
        for i in xrange(len(things)):
            for next_item in combine(things[i+1:],n-1):
                yield [things[i]] + next_item

all = list(combine(targets, 5))

for some in all:
    if sum(some) == 200:
        print some
#########################

the wierd thing is that the output has a lot of duplicates (using python2.4.1)

output:
[8, 13, 17, 23, 139]
[8, 13, 17, 23, 139]
[8, 13, 17, 31, 131]
[8, 13, 17, 61, 101]
[8, 13, 17, 73, 89]
[8, 13, 19, 29, 131]
[8, 13, 19, 29, 131]
[8, 13, 19, 29, 131]
[8, 13, 23, 29, 127]
[8, 13, 23, 67, 89]
[8, 13, 29, 37, 113]
[8, 13, 29, 61, 89]
[8, 13, 37, 41, 101]
[8, 17, 19, 29, 127]
[8, 17, 19, 67, 89]
[8, 17, 19, 29, 127]
[8, 17, 19, 67, 89]
[8, 17, 19, 29, 127]
[8, 17, 19, 67, 89]
[8, 17, 23, 73, 79]
[8, 17, 29, 67, 79]
[8, 17, 37, 41, 97]
[8, 17, 37, 41, 97]
[8, 17, 41, 61, 73]
[8, 19, 19, 23, 131]
[8, 19, 19, 41, 113]
[8, 19, 19, 23, 131]
[8, 19, 19, 41, 113]
[8, 19, 23, 37, 113]
[8, 19, 23, 61, 89]
[8, 19, 29, 31, 113]
[8, 19, 31, 41, 101]
[8, 19, 19, 23, 131]
[8, 19, 19, 41, 113]
[8, 19, 23, 37, 113]
[8, 19, 23, 61, 89]
[8, 19, 29, 31, 113]
[8, 19, 31, 41, 101]
[8, 19, 23, 37, 113]
[8, 19, 23, 61, 89]
[8, 19, 29, 31, 113]
[8, 19, 31, 41, 101]
[8, 23, 29, 61, 79]
[8, 23, 29, 67, 73]
[8, 23, 31, 37, 101]
[8, 23, 31, 41, 97]
[8, 23, 31, 41, 97]
[8, 23, 41, 61, 67]

i get the same pattern on windows and linux python 2.4.1

i checked the output of the combination generator and they're all unique values.

i also can't repeat the strange output with any other similar problems.

carl.waldbieser · 06-22-2005, 08:08 PM

The output of the combine() generator function is not all unique values. Since the list, targets, contains the value 139 more than once, then it stands to reason that various combinations that include 139 will not be unique.

Try running this modification to see what I mean:

Code:

targets=[97,101,139,41,37,31,29,89,23,19,8,13,131,19,73,97,19,139,79,67,61,17,113,127]

targets.sort()
def combine(things, n):
    if n == 0: yield []
    else:
        for i in xrange(len(things)):
            for next_item in combine(things[i+1:],n-1):
                yield [things[i]] + next_item

d = {}
for combo in combine(targets, 5):
 tup = tuple(combo)
 d[tup] = d.get(tup, 0) + 1
for key in d:
 print "%s : %d" % (str(key), d[key])

#all = list(combine(targets, 5))

#for some in all:
#    if sum(some) == 200:
#        print some

You will see that some combinations are duplicated up to 6 times.

bardinjw · 06-23-2005, 08:17 AM

Thanks
i see it now.
I was assuming the instructive problem was using a data set without duplicates. So i was racking my brain as to why the loop would repeat itself

thanks