a good algo to do this

[eight02645999]

hi
i need to do something like this
eg given a number (as a string) = "123"
there are a few combination i want to find with this string, ie
"132","321","231","312" and "213". so there are 6 combinations
altogether. i remember there's a formula for this, but forgot. Does
python have any modules/functions to do this?

thanks

 

[drochom]

hi,

try this:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465

cheers.

 

[Gerard Flanagan]

hi
i need to do something like this
eg given a number (as a string) = "123"
there are a few combination i want to find with this string, ie
"132","321","231","312" and "213". so there are 6 combinations
altogether. i remember there's a formula for this, but forgot. Does
python have any modules/functions to do this?

thanks

factorial = [ 1,
1,
2,
6,
24,
120,
720,
5040,
40320,
362880,
3628800,
39916800,
479001600,
6227020800,
87178291200,
1307674368000,
20922789888000,
355687428096000,
6402373705728000 ]

def permutation( iterable ):
length = len(iterable)
count = factorial[length]
for i in range(count):
sequence = list(iterable[:])
index = i
N = count
result = []
for j in range( length, 0, -1):
N = N / j
choice, index = index // N, index % N
result += [ sequence.pop(choice) ]
yield result

a = [ ''.join(perm) for perm in permutation('123')]

print a

['123', '132', '213', '231', '312', '321']


Gerard

 

[Gerard Flanagan]

hi
i need to do something like this
eg given a number (as a string) = "123"
there are a few combination i want to find with this string, ie
"132","321","231","312" and "213". so there are 6 combinations
altogether. i remember there's a formula for this, but forgot. Does
python have any modules/functions to do this?

thanks

factorial = [ 1,
1,
2,
6,
24,
120,
720,
5040,
40320,
362880,
3628800,
39916800,
479001600,
6227020800,
87178291200,
1307674368000,
20922789888000,
355687428096000,
6402373705728000 ]

def permutation( iterable ):
length = len(iterable)
count = factorial[length]
for i in range(count):
sequence = list(iterable[:])
index = i
N = count
result = []
for j in range( length, 0, -1):
N = N / j
choice, index = index // N, index % N
result += [ sequence.pop(choice) ]
yield result

a = [ ''.join(perm) for perm in permutation('123')]

print a

['123', '132', '213', '231', '312', '321']

Which is actually not a good algorithm at all, having just tried
'123456' - it's better for randomly-accessing a particular permutation.
There's a better 'algo' here:

http://gflanagan.net/site/python/05/Johnson.html

for getting all perms, though there's no getting away from the
factorial - IIRC, NPermutation(7) took less than a minute,
NPermutation(8) took 2 minutes and NPermutation(9) took 10 minutes on
my machine.

Also, search this group for Jack Diederich and probstat.

HTH

Gerard