当找到给定字符串的所有可能组合时，为什么字符串的第一个字符会重复自身？

Question

我的问题可能不太清楚，但我正在尝试获取所有可能的10个字符长度的字符串组合。这是我的密码：

def printPwd(set, k):
    n = len(set)
    pwdRec(set,"", n, k)

def pwdRec(set, prefix, n, k):
    if k==0:
        print(prefix)
        return

    for i in range(n):
        nPrefix = prefix + set[i]
        nk = k-1
        pwdRec(set, nPrefix, n, nk)

chars = list("abcdefghijklmno.@-_&")
length = 10

printPwd(chars, length)

它输出如下内容：

aaaaabcde@
aaaaabcde-
aaaaabcde_
aaaaabcdfg
...

我得了五个“a”，我不知道该怎么修

Answer 1

我能想到的最好的答案是“为什么不呢？”密码不能包含重复项，但代码中没有强制执行该项。相反，您的程序只是生成由字符集组成的具有特定长度的所有字符串。你知道吗

@SimonN说你的输出应该以一个10'a的字符串开始，这是正确的，确实如此。当写入文件时，第一个字符串确实是“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa。你知道吗

@alex067的建议也不能解决这个问题，因为它不仅会导致重复的字符，而且会删除列表中位于它前面的所有字符。最后一点意味着对于长度为3的密码，例如，完全有效的字符串acb、bac等被省略。当然，我们可以用prefix[i+1:]来代替prefix[i:]，但这只解决了前者的问题，而不是后者的问题。你知道吗

---

如您所知，itertools提供了可能是最好的解决方案，我将在下面介绍这一点。然而，在此之前，我发现一个递归方法非常好：

def pwd_rec(curr_charset: str, curr_pwd: str, pwd_len: int) -> List[str]:
    result_strs = []
    for idx, curr_char in enumerate(curr_charset):
        new_pwd = curr_pwd + curr_char
        if len(new_pwd) == pwd_len:
            result_strs.append(new_pwd)
        else:
            result_strs.extend(pwd_rec(curr_charset[:idx] + curr_charset[idx+1:], new_pwd, pwd_len))
    return result_strs

下面是该方法的延迟版本，使用生成器而不是列表：

def pwd_rec(curr_charset: str, curr_pwd: str, pwd_len: int) -> Iterator[str]:
    for idx, curr_char in enumerate(curr_charset):
        new_pwd = curr_pwd + curr_char
        if len(new_pwd) == pwd_len:
            yield new_pwd
        else:
            yield from pwd_rec(curr_charset[:idx] + curr_charset[idx+1:], new_pwd, pwd_len)

---

正如所承诺的，这里有一个使用itertools的方法：

import itertools as itt

def pwd_perms(charset: str, pwd_len: int) -> Iterator[str]:
    for curr in itt.permutations(charset, pwd_len):
        yield ''.join(curr)

---

如果您有任何问题，请告诉我：）

Answer 2

注意：这个答案给出了正确的输出，但我还没有弄清楚它为什么有效

你应该问的问题不是

"why do I get five 'a's?"

但是

"Why don't I get ten 'a's?"

是的。此算法的预期输出为：

aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac
aaaaaaaaad
aaaaaaaaae
...

但你的开始

aaaaj@bc
aaaaaaj@bd
aaaaaaj@be
aaaaaaj@bf

事实上，一些非常令人担忧的事情正在发生。输出甚至不是确定性的，每次运行都会得到不同的结果！我还没弄明白，所以请评论人士帮忙。如果我在debug中运行这个，然后慢慢地点击，我就会得到正确的输出。我还可以通过在函数中添加一个小sleep来纠正输出，如下所示：

import time

def printPwd(set, k):
    n = len(set)
    pwdRec(set,"", n, k)

def pwdRec(set, prefix, n, k):
    time.sleep(0.000001)
    if k==0:
        print(prefix)
        return

    for i in range(n):
        nPrefix = prefix + set[i]
        nk = k-1
        pwdRec(set, nPrefix, n, nk) #alex067's change here plus my change


chars = list("abcdefghijklmno.@-_&")
length = 10

printPwd(chars, length)

看起来我们好像被某种可变类型或非原子操作搞砸了，但我还没找到。你知道吗

alex067的评论 进行@alex067建议的更改一开始似乎可以修复输出，但在前两个循环之后会出现超出范围的错误，因为您的集合不再是n长的。实际上，您还遗漏了一些排列，其中第一个是aaaaaaaaba，因此它根本不是固定的，但至少是确定的。你知道吗