python - 在不使用 itertools 的情况下在 Python 中生成字符串的所有排列

Question

我需要生成字符串中字符的所有可能排列(重复)。如果字符串是 'abc'，输出应该是:

啊啊啊aabaac美国广播公司...加拿大广播公司cca build 银行抄送

我不能使用 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，例如!

有更好的方法吗？

Answer 1

解决此问题的一种简单方法是将字符串中的字符视为不寻常数字系统中的数字。字符串的长度是基数。因此，'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。产品(“abc”，repeat=3)