LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 06-22-2005, 11:36 AM   #1
bardinjw
Member
 
Registered: Apr 2003
Location: boston
Distribution: ubuntu debian redhat fedora
Posts: 108

Rep: Reputation: 15
Python gurus - Is this a python bug? or is it me?


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.

Last edited by bardinjw; 06-22-2005 at 11:50 AM.
 
Old 06-22-2005, 08:08 PM   #2
carl.waldbieser
Member
 
Registered: Jun 2005
Location: Pennsylvania
Distribution: Kubuntu
Posts: 197

Rep: Reputation: 32
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.
 
Old 06-23-2005, 08:17 AM   #3
bardinjw
Member
 
Registered: Apr 2003
Location: boston
Distribution: ubuntu debian redhat fedora
Posts: 108

Original Poster
Rep: Reputation: 15
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
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Processing Conflict: python-devel conflicts python< 2.3.4-13.1 guarriman Fedora 2 04-23-2009 07:02 PM
installing python library's (Python Numeric) Four Linux - Newbie 1 10-16-2005 02:31 PM
WineX, python-gnome, and python-gtk DrD Fedora 0 08-03-2004 12:11 PM
install python 2.3 ,necssary to remove python 2.2 ngan_yine Linux - Newbie 7 12-28-2003 04:07 PM
Try Python, O'reilly Learning Python haknot Programming 5 02-15-2002 08:27 AM


All times are GMT -5. The time now is 04:23 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration