Generate all possible well ordered string permutations

Question

I was asked this question at a job interview. I have been thinking about it yet couldn't find a solution.

Here is the problem: You know that a password is consisted of only letters and well ordered which means that characters in the password are in alphabetical order.

For example, a 4 digit password can be "abxz" or "aBkZ" but not "aAxz" or "baxz".

Write a function that generates all valid passwords given its length. Do not forget that it must generate all the possible combinations with upper and lower characters. Ex: "aBcd", "Abcd", "abcd", "AbCd" are all different valid passwords.

I think the algorithm must be recursive. However, nothing has worked so far. I've tried the following.

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

Please, save me from my misery.

Edit: I won't approve the solution using the itertool. I think other solution is less language dependent and can be written easily in other languages.

Answer 1

Recursion works great here. Pick a starting letter and only iterate from remaining letters, recursing on both upper and lower case and bumping the start letter up along the way. The base case is when the length of the string we're building is the same as the target length.

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)

Output:

239200

ABCD
ABCd
ABCE
ABCe
ABCF
ABCf
ABCG
ABCg
ABCH
ABCh
...
WxyZ
Wxyz
wXYZ
wXYz
wXyZ
wXyz
wxYZ
wxYz
wxyZ
wxyz