Re: How to generate all permutations of a string?

Discussion in 'Python' started by Maric Michaud, Jun 22, 2006.

1. Maric MichaudGuest

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
>

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

Maric Michaud, Jun 22, 2006