生成Python字符串中所有的变位词

Question

今天我在思考这个问题，想出了以下伪代码（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

然而，我想知道一种Python风格的方法来执行此操作：
anagram = c + anagram(string - {c})

我该如何从字符串中删除那个字符？例如：

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

谢谢

- cybertextron

---

我认为变位词需要是指定语言中的合法单词。在我看来，排列组合可能更合适。 - Robin Andrews

Answer 1

为什么不直接使用 itertools 呢？

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

这份文档中还包含了如何进行排列的代码。

---

编辑：

不使用 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))

没有使用 itertools 和 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

结果：

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

- sloth

---

BigYelloCactus，我喜欢你的回答，但我需要一个递归方法，如所示，它可以被任何编程语言（例如：C）使用。 - cybertextron

Answer 2

使用 itertools 模块。

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

- Lanaru

---

使用 list(''.join etc) 或者 [''.join etc] 任意一种方式即可，不需要同时使用两种。 - DSM

我需要一个递归的方法，就像所示的那样，可以被任何编程语言（比如C语言）使用，但你做得很好！ - cybertextron

Answer 3

需要注意的是，如果字符串包含多个相同字母的实例-重复排列，则@sloth的答案会给出稍微意外的结果：

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

导致结果：

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

如果这不是你想要的结果，使用 'set' 将会消除重复项。但如果你想要一个列表，你需要重新列出来（另外 'set' 不会保持顺序，所以需要使用 'sorted'）：

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

导致以下结果：

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

- deepstructure

Answer 4

这里有一些建议，包装成一个新的脚本，称为anagram

$ anagram hit
hit
hti
iht
ith
thi
tih

变位词

#!/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)

- Brad Parks

Answer 5

你可以将单词转换为列表，运行 remove 然后使用 join 将其重新组合。

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

- mjgpy3