Function to return all permutations of password suggestions

user_11500112 0
Viewed 197

So we have a (static) map that specifies letters we want to replace with special characters. Except we don't want to return just one string with all the replacements, we want to return every permutation achievable by replacing one or more characters of our original password. Here is one such map:

{'i': '!', 'a': '@', 's': '$', 'o': '0', 'E': '3'}

Here is what I have so far in Python:

def permute_password(password: str, chars_map: dict) -> List[str]:
        def find(password, seen, ans):
            if len(password)==0:
                ans.append(seen)
                return 
            for i in range(len(password)):
                pass_cpy=password.copy()
                if chars_map.get(pass_cpy[i]):
                    pass_cpy[i] = chars_map.get(pass_cpy[i])
                find(pass_cpy, seen+pass_cpy[i]+pass_cpy[i+1:], ans)
            return ans
        ans=[]
        return find(password, "", ans)

From what I can tell, my problem lies in the for loop. Specifically, I'm not sure how to set up the recursion.

And this is what it would like to run the function:

special_chars = {'i': '!', 'a': '@', 's': '$', 'o': '0', 'E': '3'} 
print('\n'.join(permute_password("password", special_chars)))

And this is the desired output:

p@ssword
p@$sword
pa$sword
p@s$word
p@$$word
pa$$word
pas$word
p@ssw0rd
p@$sw0rd
pa$sw0rd
p@s$w0rd
p@$$w0rd
pa$$w0rd
pas$w0rd
passw0rd
permutation python
2 Answers

A recursive solution:

def permutePassword(p, special_chars, start=0):
    for i, ch in list(enumerate(p))[start:]:
        if ch in special_chars:
            s = p[:i] + special_chars[ch] + p[i+1:]
            yield s
            yield from permutePassword(s, special_chars, i)

specialChars = {'i':'!','a':'@','s':'$','o':'0','E':'3'}

for p in permutePassword("password", specialChars):
    print(p)

Prints:

p@ssword
p@$sword
p@$$word
p@$$w0rd
p@$sw0rd
p@s$word
p@s$w0rd
p@ssw0rd
pa$sword
pa$$word
pa$$w0rd
pa$sw0rd
pas$word
pas$w0rd
passw0rd

Here is an implementation without yield and enumerate (credit due to the original author):

def permute_password(p, special_chars, start=0, res=set()):
for i in range(len(p[start:])):
    if p[i] in special_chars:
        s = p[:i] + special_chars[p[i]] + p[i+1:]
        res.add(s)
        permute_password(s, special_chars, i)
return res
user_100359850

Instead of using a recursive function you could consider using a stack (i.e., making your function iterative) instead if makes it easier to follow for you:

def permutePassword(password: str, charsMap: dict) -> [int]:
    permutations = []
    len_of_password = len(password)
    stack = [(list(password), 0)]
    while stack:
        curr, index = stack.pop()
        if index == len_of_password:
            permutations.append(''.join(curr))
        else:
            stack.append((curr, index + 1))
                if curr[index] in charsMap:
                    curr[index] = charsMap[curr[index]]
                    stack.append((curr.copy(), index + 1))
    return permutations[:-1]  # last permutation will be the original password


specialChars = {'i': '!', 'a': '@', 's': '$', 'o': '0', 'E': '3'}
permutations = permutePassword("password", specialChars)
print('\n'.join(permutations))

Output:

p@$$w0rd
p@$$word
p@$sw0rd
p@$sword
p@s$w0rd
p@s$word
p@ssw0rd
p@ssword
pa$$w0rd
pa$$word
pa$sw0rd
pa$sword
pas$w0rd
pas$word
passw0rd

Try it out here

user_63282560
Related