a good algo to do this

[eight02645999@yahoo.com]

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","23 1","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]

Re: a good algo to do this

hi,

try this:

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

cheers.

[Gerard Flanagan]

Re: a good algo to do this


eight02645999@y ahoo.com wrote:[color=blue]
> 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","23 1","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[/color]

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

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(ch oice) ]
yield result

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

print a

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


Gerard

[Gerard Flanagan]

Re: a good algo to do this

Gerard Flanagan wrote:[color=blue]
> eight02645999@y ahoo.com wrote:[color=green]
> > 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","23 1","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[/color]
>
> factorial = [ 1,
> 1,
> 2,
> 6,
> 24,
> 120,
> 720,
> 5040,
> 40320,
> 362880,
> 3628800,
> 39916800,
> 479001600,
> 6227020800,
> 87178291200,
> 1307674368000,
> 20922789888000,
> 355687428096000 ,
> 640237370572800 0 ]
>
> 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(ch oice) ]
> yield result
>
> a = [ ''.join(perm) for perm in permutation('12 3')]
>
> print a
>
> ['123', '132', '213', '231', '312', '321']
>
>[/color]

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