a good algo to do this

[Gerard Flanagan]

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