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

Stack Overflow用户

提问于 2020-01-10 17:19:43

回答 2查看 627关注 0票数 1

我是在面试时被问到这个问题的。我一直在想这件事，但却找不到解决办法。

问题是:您知道密码只由字母和有序组成，这意味着密码中的字符是按字母顺序排列的。

例如，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))

求你了，把我从痛苦中拯救出来。

编辑:我不会批准使用迭代工具的解决方案。我认为其他解决方案不那么依赖于语言，而且可以很容易地用其他语言编写。

python

algorithm

permutation

password-generator

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-01-10 17: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
wxyz

票数 1

Stack Overflow用户

发布于 2020-01-10 18: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))