递归Python函数生成字母异位词列表

Question

经过很多思考和查资料，我还是搞不明白这个问题。我刚开始学Python，语法对我来说有点难。虽然我对自己想做的事情和递归的概念有个大致的了解，但把它写成Python代码却让我很头疼。

简单来说，我想把一个单词的所有排列组合添加到一个列表里（不允许有重复的字符），然后可以被其他程序或函数调用。

我对返回命令和如何处理空格感到很困惑。我希望递归函数在展开的时候能“返回”一些东西，但我又不想让它在所有字符都遍历完、所有排列组合都生成之前就停止。当我运行下面的代码时，似乎什么都没有发生。

def permutations(A, B = ''):
    assert len(A) >= 0
    assert len(A) == len(set(A))
    res = []
    if len(A) == 0: res = res.extend(B)
    else:
        for i in range(len(A)):
            permutations(A[0:i] + A[i+1:], B + A[i])
    return res

permutations('word'))

如果我运行下面的代码，它会在我的显示面板上正常打印出来，但我不知道怎么把它转换成其他程序可以使用的输出格式，比如一个列表。

def permutations(A, B = ''):
    assert len(A) >= 0
    assert len(A) == len(set(A))
    if len(A) == 0: print(B)
    else:
        for i in range(len(A)):
            permutations(A[0:i] + A[i+1:], B + A[i])

permutations('word')

请问有人能帮我一下吗，趁我还有点头发！非常感谢。

谢谢

Jon

Answer 1

我会这样做：

def permute_nondupe_letters_to_words(iterable):
    return (''.join(i) for i in itertools.permutations(set(iterable)))

然后使用它：

word = 'word'
permutation_generator = permute_nondupe_letters_to_words(word)

bucket_1, bucket_2 = [], []
for i in permutation_generator:
    bucket_1.append(i)
    if i == 'owdr':
        break

for i in permutation_generator:
    bucket_2.append(i)

还有

print(len(bucket_1), len(bucket_2))

输出结果是：

(10, 14)

Answer 2

像这样吗？

from itertools import permutations
a = [x for x in permutations('word')]
print a

输出结果：

>>[('w', 'o', 'r', 'd'), ('w', 'o', 'd', 'r'), ('w', 'r', 'o', 'd'),
>>('w', 'r', 'd', 'o'), ('w', 'd', 'o', 'r'), ('w', 'd', 'r', 'o'), 
>>('o', 'w', 'r', 'd'), ..............

编辑：

我刚意识到你说不允许有重复的字符。对于'word'来说这没什么关系，但假设你有'wordwwwdd'。那么你可以这样做：

[x for x in permutations(''.join(set('wordwwwdd')))] 

不过这样会打乱顺序，因为使用了集合，所以结果会变成这样：

>> [('r', 'o', 'w', 'd'), ('r', 'o', 'd', 'w'), ('r', 'w', 'o', 'd')....

Answer 3

基本上，你的错误在于

res = res.extend(B)

.extend() 这个方法并不会返回一个新的列表，而是直接修改了原来的列表。

另一个问题是，你没有使用递归调用的返回值。

这里有一种方法可以修复你的代码：

def permutations(A, B = ''):
    assert len(A) >= 0
    assert len(A) == len(set(A))
    if len(A) == 0:
        return [B]
    else:
        res = []        
        for i in range(len(A)):
            res.extend(permutations(A[0:i] + A[i+1:], B + A[i]))

        return res

print permutations('word')