sorting question

[Alistair Watts]

  A little recursive solution to the problem.

  The idea here is firstly consider the base case of a string of length
one.  Easy, it's just that string.  

  Secondly, for a string of length n, where n>1 choose each character in
turn for the start of the result and use the characters left over to
construct the tail.

  The tail is all the combinations of the remaining letters.  Which is
the same problem again except the string is now of length n-1.  So
recurse until we reach the base case.

  Not sure if this is faster than Alex's code, but it's a few line less.

  Regards...

Alistair

-----------------------------------

text = 'bar'

def f(s):
  if len(s) == 1:
    return s[0]
  r = []
  for i in range(len(s)):
    for rest in f(s[:i] + s[i+1:]):
      r.append(s[i] + rest)
  return r

>>> f(text)
['bar', 'bra', 'abr', 'arb', 'rba', 'rab']

-----------------------------------

Alex Martelli wrote:
> 
> "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
> 
> --
> http://mail.python.org/mailman/listinfo/python-list

-- 
-----------------------------------
Business Collaborator Team
Enviros Software Solutions
http://www.businesscollaborator.com
-----------------------------------