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

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))    

求你救我脱离痛苦。

编辑： 我不会批准使用迭代工具的解决方案。我认为其他解决方案对语言的依赖性较小，可以用其他语言轻松编写。

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))

Answer 2

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

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