Question

Ok...similar to JAZZVBOXDOC....I've got a bunch of FOR loops, but seem to be utilizing the 'break' function erroneously. How do I get combinations/permutations without repetition.

My attempt here: http://codepad.org/QwYXrOnP

this doesn't cover all of them.....someone??? Please help

Answer 1

Can you describe in pseudo-code what you are trying to do in this application.

Answer 2

I'd like to run all combinations of these three letters ... without repetition. ie: 'aac' NOT allowed

Answer 3

which do you want, combinations or permutations?

Answer 4

I suppose I want to know how to do both, but for this specific task I looking for combinations without repetition

Answer 5

one way might be:
have you ever counted in binary? say you have a 3 letter hand and a 3 bit integer -
if you count from 0 to (2 ** 3)-1 every one of those counts has a unique bit pattern and they encompass all the combinations of ones and zeroes in a three bit integer. if you could somehow take advantage of that by relating the bit positions to the positions of the letters in the hand then you might be able to generate all of the combinations of letters. if those combinations were sorted they would work very well with the re-arranged dictionary.

Answer 6

bray, I don't know if you got an answer to your question or not, but i was able to get what I needed using the itertools module. Google it. It has a method called combinations (itertools.combinations) that is perfect for what we are trying to do. If you'd like, let me know and ill show you the code i used.

Answer 7

@jazzboxdoc : I also found that module a while back...but for some reason it doesn't seem to import correctly. I tried even tried directly importing into my shell to no avail. 2.7 can use it right? I'm interested to see your code...please paste.

@bwCA: I'm familiar with counting in base 2, but the relationship is still spinning my head. I see the similarities, for example 2**3 is 8...binary = 4 digits : 1000 . counting all the way to 15, ie: using all possible binary combinations in the 4 digits to represent all possible combinations of a 3 digit hand....lost from here. Lead me along some more.....4 digits to 3 options???? How do I map this?

judging from your post..I could be way off with the 4 digits. So using (2**3) -1 ie 7, or 111 in binary which could represent all letters being used. 100 = a, 010 = b, 001 =c, Where as 110 would be 'ab' and 'ba'. I can't seem to represent 'ab' and 'ba' any differently. if 110 = ab and ba, how do I code this. I'm fairly certain I can find a way to count in binary, but am struggling with how to represent each 1 as a particular letter as well. Thanks

Answer 8

(2 ** 3) - 1
you shouldn't have to google itertools. the Python documentation should be installed on your computer. you can find it online here (2.7) http://docs.python.org/. it is part of the standard library for 2.7.

if you want both ab and ba then you are looking for permutations (the order matters) and the method i described wouldn't work - it generates combinations.

Python has a lot of really cool string stuff. you can represent an integer in binary as a string then you can iterate over the string and choose letters based on the zeroes and one's.
here is my combo generator compared to itertools.combinations()
http://dpaste.com/689504/

Answer 9

@bray: yes 2.7. If importing itertools doesn't work, try copying the code they provide in py docs (their definition) and referencing it manually. You can run with the binary idea, but I'm am unfamiliar with binary and don't time to play with it right now. Heres the code i used for PickBestWordFaster:

def PickBestWordFaster(hand,rearrange_dict):
"""
Return the highest scoring word from rearrange_dict that can be made with the given hand.

return '.' if no words can be made with the given hand.
"""
letters=''
for letter in hand:
for x in range(hand[letter]): ## one letter for each time it appears in hand
letters+=letter
sub_multisets=[]
for n in range(len(letters)):
sub_multiset=[''.join(list(each)) for each in itertools.combinations(letters,n+1)]
sub_multisets+=sub_multiset

## a check

if TotalCombinations(len(letters))!=len(sub_multisets):
print 'ERROR-TotalCombinations(len(letter))!=len(sub_multisets)',TotalCombinations(len(letters)),len(sub_multisets)
exit()

highest_score=0
highest_score_word=''
for sub_multiset in sub_multisets:
sorted_letters=''.join(sorted(sub_multiset))
if sorted_letters in rearrange_dict:
score= GetWordScore(rearrange_dict[sorted_letters],HAND_SIZE)
if score>highest_score:
highest_score=score
highest_score_word=rearrange_dict[sorted_letters]

if highest_score==0:
##check
if highest_score_word!='':
print "ERROR- highest score==0 and word!= '' "
print highest_score,repr(highest_score_word)
exit()
return '.'
else:
return highest_score_word

Sorry, I'm not familiar enough with this site to know how to use a third party site to post code. The above code uses a def i wrote to calculate total combinations of a given string of all lengths. It uses it as check and heres the code:

def TotalCombinations(n):
"""
returns the total number of combinations, as an integer, that can be made from a seq of len(n).

Combinations can have any length.

"""
combinations=0

numbers=range(n,0,-1)

iterations=1
while iterations != n+1:
temp=1
for i in range(iterations):
temp*=numbers[i]
temp/=math.factorial(iterations)
combinations+=temp
iterations+=1
return combinations

Answer 10

Thanks guys...this will give me something to chew for a while. I'll let you know when I comprehend it all.