cybertextron - 1 year ago 115
Python Question

producing all the anagrams from a string python

I was thinking about this problem today, and I came with the following pseudocode (Python 3.2) :

def anagrams( string ):

for c in string:
anagram = c + anagram( string - {c} ) # remove the char from its position in the string
print(anagram)

return

def main():

word = "abcd"
anagrams( word )

return

However, I'd like to know a pythonic way to do this operation:
anagram = c + anagram( string - {c} )

How could I remove that char from the string? so for example:

"abc" -> 'a' + "bc" -> 'a' + 'b' + "c" -> 'a' + 'b' + 'c' = 'abc'
+ "cb" -> 'a' + 'c' + "b" -> 'a' + 'c' + 'b' = 'acb'
-> 'b' + "ac" -> 'b' + 'a' + "c" -> 'b' + 'a' + 'c' = 'bac'
+ "ca" -> 'b' + 'c' + "a" -> 'b' + 'c' + 'a' = 'bca'
-> 'c' + "ba" -> 'c' + 'b' + "a" -> 'c' + 'b' + 'a' = 'cba'
+ "ab" -> 'c' + 'a' + "b" -> 'c' + 'a' + 'b' = 'cab'

Thanks

Why not just use itertools?

>>> import itertools
>>> ["".join(perm) for perm in itertools.permutations("abc")]
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

The documentation also contains code how the permutation is done.

Edit:

def all_perms(elements):
if len(elements) <=1:
yield elements
else:
for perm in all_perms(elements[1:]):
for i in range(len(elements)):
yield perm[:i] + elements[0:1] + perm[i:]

word = "abc"
print list(all_perms(word))

Without itertools and without generators:

def all_perms(elements):
if len(elements) <=1:
return elements
else:
tmp = []
for perm in all_perms(elements[1:]):
for i in range(len(elements)):
tmp.append(perm[:i] + elements[0:1] + perm[i:])
return tmp

Result:

['abc', 'bac', 'bca', 'acb', 'cab', 'cba']

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download