How to generate all permutations of a string?

Maric Michaud maric at aristote.info
Thu Jun 22 12:24:08 CEST 2006


Le Jeudi 22 Juin 2006 10:07, Girish Sahani a écrit :
> Hi guys,
>   I want to generate all permutations of a string. I've managed to
> generate all cyclic permutations. Please help :)
>
Here is mine, maybe more versatile :


def permute(iterable) :
     if len(iterable) == 1 : yield iterable
     else :
         next = permute(iterable[1:])
         for i in next :
             if isinstance(iterable[0], basestring) :
                 elt = iterable.__class__(iterable[0])
             else : elt = iterable.__class__((iterable[0],))
             for j, k in enumerate(i) : yield i[0:j] + elt + i[j:]
             yield i + elt




In [2]: list(permute((1, 2, 3)))
Out[2]: [(1, 2, 3), (2, 1, 3), (2, 3, 1), (1, 3, 2), (3, 1, 2), (3, 2, 1)]

In [3]: list(permute('abc'))
Out[3]: ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']

In [4]: list(permute('aba'))
Out[4]: ['aba', 'baa', 'baa', 'aab', 'aab', 'aba']

In [5]: set(permute('aba'))
Out[5]: set(['aba', 'aab', 'baa'])

In [6]: list(permute([1, 3, 3]))
Out[6]: [[1, 3, 3], [3, 1, 3], [3, 3, 1], [1, 3, 3], [3, 1, 3], [3, 3, 1]]

In [7]: set(permute([1, 3, 3])) # warning
---------------------------------------------------------------------------
exceptions.TypeError                                 Traceback (most recent 
call last)

/home/maric/<ipython console>

TypeError: list objects are unhashable

In [8]: set(permute((1, 3, 3)))
Out[8]: set([(3, 3, 1), (3, 1, 3), (1, 3, 3)])

regards,

-- 
_____________

Maric Michaud
_____________

Aristote - www.aristote.info
3 place des tapis
69004 Lyon
Tel: +33 426 880 097



More information about the Python-list mailing list