CODEWITHSUNDEEP
pythonalgorithmpermutationpassword-generator
a_a_a
a_a_a

Reputation: 283

Generate all possible well ordered string permutations

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.

Upvotes: 1

Views: 1142

Answers (2)

ggorlen
ggorlen

Reputation: 57115

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

Upvotes: 1

Kelly Bundy
Kelly Bundy

Reputation: 27629

Using itertools, finds the same 239200 strings as @ggorlen's.

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)

And a variation, not sure which one I like better:

def all_alphabetical_pw(length):
    for c in combinations(zip(ascii_uppercase, ascii_lowercase), length):
        for p in product(*c):
            yield ''.join(p)

Both work by producing combinations like (('D', 'd'), ('I', 'i'), ('N', 'n'), ('O', 'o')) and then their products, giving tuples like ('D', 'i', 'n', 'O') which just need joining. The two solutions differ only by when I turn letters like 'D' into pairs like ('D', 'd').

The first version does it after producing combinations like ('D', 'I', 'N', 'O'), turning each such combination into a combination of (upper,lower) pairs.

The second version does it before producing combinations, instead building pairs for the entire alphabet once. That's more efficient, and it looks cleaner. Ok, I prefer this one now.

Benchmarks:

@ggorlen's  0.199 seconds
my first    0.094 seconds
my second   0.072 seconds

Measured like this:

timeit(lambda: list(all_alphabetical_pw(4)), number=100) / 100

Oh, one more. Takes 0.056 seconds so it's fastest, but I like it less:

def all_alphabetical_pw(length):
    for c in combinations(zip(ascii_uppercase, ascii_lowercase), length):
        yield from map(''.join, product(*c))

Upvotes: 2

Related Questions