在不使用迭代工具的情况下在Python中生成字符串的所有排列

问题描述

我需要生成字符串中所有可能的字符排列(带有重复)。如果字符串为‘abc’，则输出应为：

AAA AAB AAC ABC ..。 CBC CCA 建行 Ccc

我不能使用IterTools模块，也不想使用递归(因为这只是一个示例。我真正需要的是输出数百万个排列，并且我害怕耗尽内存)

我可以这样做：

s = 'abc'

for c1 in range(0, 3):
    for c2 in range(0, 3):
        for c3 in range(0, 3):
            print(s[c1]+s[c2]+s[c3])

基本上，我的for循环数与字符串的字符数一样多。 现在假设字符串的长度为10，例如！

有没有更好的方法？

---

解决方案

解决此问题的一种简单方法是将字符串中的字符视为特殊数字系统中的数字。弦的长度是底数。因此，'abc'的排列(重复)对应于基数3中从0到3**3-1的数字，其中'a'是数字0，'b'是1，'c'是2。

def permutations_with_repetition(s):
    base = len(s)
    for n in range(base**base):
        yield "".join(s[n // base**(base-d-1) % base] for d in range(base))

示例运行：

>>> for p in permutations_with_repetition("abc"):
    print(p)


aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

如果允许使用itertools，您会希望itertools.product带有repeat关键字参数：itertools.product("abc", repeat=3)