生成所有可能的有序字符串排列
我是在面试时被问到这个问题的。我一直在想这件事，但却找不到解决办法。
问题是:您知道密码只由字母和有序组成，这意味着密码中的字符是按字母顺序排列的。
例如，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)) 求你了，把我从痛苦中拯救出来。
编辑:我不会批准使用迭代工具的解决方案。我认为其他解决方案不那么依赖于语言，而且可以很容易地用其他语言编写。
回答 2
Stack Overflow用户
发布于 2020-01-11 01:36:02
递归在这里效果很好。选择一个起始字母，只从剩下的字母中迭代，在大写和小写中递归，并在整个过程中将起始字母向上推。基本情况是，当我们构建的字符串的长度与目标长度相同时。
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
wxyzStack Overflow用户
发布于 2020-01-11 02:19:22
使用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))https://stackoverflow.com/questions/59690859
复制相似问题
腾讯云开发者
