生成所有可能的有序字符串置换

Question

在面试中有人问我这个问题。我一直在想，但找不到解决方案。

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

例如，一个四位数的密码可以是“ 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))    

请，从痛苦中救我。

Answer 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

Answer 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'))的combinations然后是它们的products >>来工作，给出像('D', 'i', 'n', 'O')这样的元组只需要连接。两种解决方案的区别仅在于当我将'D'之类的字母变成('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))