1

我在一次工作面试中被问到这个问题。我一直在考虑它，但找不到解决方案。

这就是问题所在：您知道密码仅由字母组成且顺序良好，这意味着密码中的字符按字母顺序排列。

例如，4 位密码可以是“abxz”或“aBkZ”，但不能是“aAxz”或“baxz”。

编写一个函数，根据其长度生成所有有效密码。不要忘记它必须生成所有可能的大小写组合。例如：“aBcd”、“Abcd”、“abcd”、“AbCd”都是不同的有效密码。

我认为算法必须是递归的。然而，到目前为止，没有任何效果。我试过以下。

def func(number, start_letter ='A',  match = ''):
    if number == 0:
        print(match)
    else:
        for i in range(ord(start_letter), 70):
            func(number-1, chr(ord(start_letter)+1),match + chr(i))

请把我从痛苦中拯救出来。

编辑：我不会批准使用 itertool 的解决方案。我认为其他解决方案对语言的依赖性较小，可以很容易地用其他语言编写。

4

2 回答 2

2

使用itertools, 找到与 @ggorlen 相同的 239200 个字符串。

from string import ascii_uppercase
from itertools import combinations, product

def all_alphabetical_pw(length):
    for c in combinations(ascii_uppercase, length):
        for p in product(*zip(c, map(str.lower, c))):
            yield ''.join(p)

还有一个变体，不确定我更喜欢哪一个：

def all_alphabetical_pw(length):
    for c in combinations(zip(ascii_uppercase, ascii_lowercase), length):
        for p in product(*c):
            yield ''.join(p)

两者都通过产生组合(('D', 'd'), ('I', 'i'), ('N', 'n'), ('O', 'o'))来工作，然后是它们的产品，给出('D', 'i', 'n', 'O')只需要加入的元组。这两种解决方案的不同之处仅在于我将字母 like'D'变成了对 like ('D', 'd')。

第一个版本是在生成类似 的组合之后执行此操作('D', 'I', 'N', 'O')，将每个这样的组合变成（上、下）对的组合。

第二个版本在生成组合之前完成它，而不是为整个字母表构建一次。这样更有效率，而且看起来更干净。好的，我现在更喜欢这个。

基准：

@ggorlen's  0.199 seconds
my first    0.094 seconds
my second   0.072 seconds

像这样测量：

timeit(lambda: list(all_alphabetical_pw(4)), number=100) / 100

哦，再来一张。需要 0.056 秒，所以它是最快的，但我不喜欢它：

def all_alphabetical_pw(length):
    for c in combinations(zip(ascii_uppercase, ascii_lowercase), length):
        yield from map(''.join, product(*c))
于 2020-01-11T02:19:22.560 回答
1

递归在这里工作得很好。选择一个起始字母并仅从剩余的字母中迭代，在大写和小写上递归并沿途向上碰撞起始字母。基本情况是我们正在构建的字符串的长度与目标长度相同。

def all_alphabetical_pw(length, start=65, pw=""):
    if len(pw) == length:
        yield pw
    else:
        for i in range(start, 91):
            yield from all_alphabetical_pw(length, i + 1, pw + chr(i))
            yield from all_alphabetical_pw(length, i + 1, pw + chr(i).lower())

if __name__ == "__main__":
    pws = list(all_alphabetical_pw(4))
    print(len(pws), "\n")

    for pw in pws[:10]: 
        print(pw)

    print("...")

    for pw in pws[-10:]: 
        print(pw)

输出：

239200

ABCD
ABCd
ABCE
ABCe
ABCF
ABCf
ABCG
ABCg
ABCH
ABCh
...
WxyZ
Wxyz
wXYZ
wXYz
wXyZ
wXyz
wxYZ
wxYz
wxyZ
wxyz
于 2020-01-11T01:36:02.823 回答