producing all the anagrams from a string python

Question

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

I think anagrams need to be legitimate words in a specified language. Permutations would be a better term here, IMO. — Robin Andrews, Oct 19 '22 at 22:04

score 33 · Accepted Answer · edited May 23 '17 at 11:33

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:

Without itertools:

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']

BigYelloCactus, I loved you answer, but I needed a recursive approach as illustrated, which could be used by any programming language (aka: C) — cybertextron, Aug 16 '12 at 14:42

Lanaru · Answer 2 · 2012-08-16T14:44:50.723

6

Use the itertools module.

import itertools
perms = [''.join(perm) for perm in itertools.permutations('abc')]

edited Aug 16 '12 at 14:44

answered Aug 16 '12 at 14:39

Lanaru

9,421
7
38
64

1

Either `list(''.join etc)` or `[''.join etc]` would work on its own; no need to do both. – DSM Aug 16 '12 at 14:41
I needed a recursive approach as illustrated, which could be used by any programming language (aka: C), but +1 for your good job! – cybertextron Aug 16 '12 at 14:48

score 4 · Answer 3 · answered Nov 10 '16 at 02:41

Just to note, @sloth's answer gives a slightly unexpected result if the string contains more than one instance of a letter - duplicate permutations:

["".join(perm) for perm in itertools.permutations('aabc')]

Results in:

['aabc',
 'aacb',
 'abac',
 'abca',
 'acab',
 'acba',
 'aabc',
 'aacb',
 'abac',
 'abca',
 'acab',
 'acba',
 'baac',
 'baca',
 'baac',
 'baca',
 'bcaa',
 'bcaa',
 'caab',
 'caba',
 'caab',
 'caba',
 'cbaa',
 'cbaa']

If this isn't the desired result, using 'set' will eliminate the dups. Although if you want a list, you'll need to relist (also 'set' doesn't maintain order so use 'sorted'):

sorted(set(["".join(perm) for perm in itertools.permutations("aabc")]))

Results in:

['aabc',
 'aacb',
 'abac',
 'abca',
 'acab',
 'acba',
 'baac',
 'baca',
 'bcaa',
 'caab',
 'caba',
 'cbaa']

score 0 · Answer 4 · answered Aug 16 '12 at 14:41

0

You can cast the word to a list, run remove and then use join to get it back together again.

word = 'abca'
letters = list(word)
letters.remove('a')  # Only deletes the first 'a'
word = ''.join(letters)

answered Aug 16 '12 at 14:41

mjgpy3

8,597
5
30
51

score 0 · Answer 5 · answered Feb 02 '22 at 13:09

Here's some of the suggestions wrapped up to make a new script, called anagram

$ anagram hit
hit
hti
iht
ith
thi
tih

anagram

#!/usr/bin/env python3
import argparse
import itertools
import sys

parser = argparse.ArgumentParser()
parser.add_argument("word", help="A word to generate anagrams for.")
args = parser.parse_args()

perms = [''.join(perm) for perm in itertools.permutations(args.word)]
for perm in perms:
    print(perm)

producing all the anagrams from a string python

5 Answers5

anagram

Linked