python - 生成所有可能的有序字符串排列

Question

我在面试时被问到这个问题。我一直在想这个问题，但没有找到解决办法。

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

例如，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 的解决方案。我认为其他解决方案较少依赖于语言，并且可以轻松地用其他语言编写。

Answer 1

使用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')< 这样的元组 只需加入即可。这两种解决方案的区别仅在于当我将 '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))