a good algo to do this
Gerard Flanagan
grflanagan at yahoo.co.uk
Mon Mar 6 17:43:23 CET 2006
Gerard Flanagan wrote:
> eight02645999 at yahoo.com wrote:
> > 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
More information about the Python-list
mailing list