sorting question

[Steve Purcell]

dsavitsk wrote:
> i would like to iterate through all possible combinations of the characters
> in a string, and i am not thinking very clearly about how to approach this.
> that is, if the initial string is 'bar', i want to print
> ['bar', 'bra', 'abr', 'arb', 'rba', 'rab']
> any hints?

The following works for me:

def permute(choices, fixed=''):
    bag = []                   
    numchoices = len(choices)
    for pos in range(numchoices):
        start = choices[pos]
        rest = choices[:pos] + choices[pos+1:]
        bag.extend(permute(rest, fixed + start))
        if numchoices == 1: bag.append(fixed + start + rest)
    return bag

print permute('bar')
print permute('1234')

It produces the following output:

['bar', 'bra', 'abr', 'arb', 'rba', 'rab']
['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341 '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132 '4213', '4231', '4312', '4321']


With longer strings, you probably don't want to store the results in memory,
so you can use a visitor function instead of a list:

def permute2(choices, visitfunc, fixed=''):
    numchoices = len(choices)              
    for pos in range(numchoices):
        start = choices[pos]
        rest = choices[:pos] + choices[pos+1:]
        permute2(rest, visitfunc, fixed + start)
        if numchoices == 1: visitfunc(fixed + start + rest)

permutations = []
permute2('1234567', permutations.append)  # pretty silly example of a visitor
print permutations

If your strings have repeated characters and you want only unique combinations:

permutations = {}
def visitor(v):
    permutations[v] = None
permute2('ababcbed', visitor)
print permutations.keys()


Hope that helps,

-Steve

-- 
Steve Purcell, Pythangelist
Get testing at http://pyunit.sourceforge.net/
Available for consulting and training.
"Even snakes are afraid of snakes." -- Steven Wright