sorting question

[Alex Martelli]

"dsavitsk" <dsavitsk at e-coli.net> wrote in message
news:tmlg6.61202$Ch.11526305 at newsrump.sjc.telocity.net...
> 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?

Perhaps not very fast, but, IMHO, pretty cool:

class Perm:
    def __init__(self, seq):
        self._seq = list(seq)
        self._len = len(self._seq)
    def __getitem__(self, x):
        index = x
        indices = [-1]*(self._len-1)
        for n in range(self._len,1,-1):
            index,indices[self._len-n] = divmod(index,n)
        if index: raise IndexError,x
        result = self._seq[:]
        for i in range(len(indices)):
            index = i+indices[i]
            result[i],result[index] = result[index],result[i]
        return result

and now

for p in Perm('bar'):
    print ''.join(p)

>>> for p in Perm('bar'):
...     print ''.join(p)
...
bar
abr
rab
bra
arb
rba
>>>

the idea is to associate to each number between 0 and
one less than the factorial of N (where N is the length
of the sequence being permuted) a specific permutation,
which is a list of N integers -- the first in
range(0,N), the second in range(0,N-1), ... the last
always 0 (so, no need to record or compute it).  As
usual for enumeration tasks, it looks a bit like a
problem of 'counting in some base', except that, here,
it's several bases -- N for the first digit, N-1 for
the second one, and so on.  Unfortunately I don't think
there is a close-form way to get the list of N integers
from the number it represents, whence the loop with
the divmod in it.

The second half of the __getitem__ method then gets
from the list of numbers to an actual permutation, by
a way that will remind one of 'Knuth shuffling' if one
has ever programmed the latter:-).  It can be done
in other good ways, though.


Alex