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

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

递归在这里很有效。选择一个起始字母，只从剩余的字母开始迭代，在大写和小写上递归，并在整个过程中将起始字母向上推。基本情况是我们正在构建的字符串的长度与目标长度相同。

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')) 然后是它们的产品，给出像 ('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))

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

Generate all possible well ordered string permutations

python

algorithm

permutation

password-generator