Tag: permutation

What's the best way to enumerate permutations of deck of cards?

I’m looking to make a function that would assign a value to a specific shuffle of cards.

The function has to be bijective. The deck has 52 cards so there are 52! different shuffles, therefore the domain is the set of all permutations of 52 cards, and the codomain is integers from 1 to 52!.

What would be the best algorithm to do this fast and efficiently?

Solution:

To encode a permutation to a value in pseudocode:

A = list of cards
value = 0
for i in range(52):
   cards_left = 52-i
   let pos = index of card i in A 
   delete A[pos]
   value = value * cards_left + pos

At the end, A will be an empty list, and value has a number representing the permutation.

To decode:

A = []
value is an input
for i in reversed(range(52)):
   cards_left = 52-i
   pos = value % cards_left
   value = value / cards_left
   Insert card i at index pos in A

At end, A should contain the original permutation.

Example Python code:

B=[3,2,0,1,4]

def encode(A):
    value = 0
    n = len(A)
    A=A[:]
    for i in range(n):
       cards_left = n-i
       pos = A.index(i)
       del A[pos]
       print pos,cards_left
       value = value * cards_left + pos
    return value

def decode(value,n):
    A=[]
    for i in range(n-1,-1,-1):
       cards_left = n-i
       value,pos = divmod(value, cards_left)
       A.insert(pos,i)
    return A

v=encode(B)
print v
print decode(v,len(B))

How to make all of the permutations of a password for brute force?

So I was trying to make a program that brute forces passwords.

Firstly, I made a program for a password of length 1:

password = input('What is your password?\n')
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'

def brute_force():
    for char in chars:
        if char == password:
            return char

print(brute_force())

Then I edited it for a password of length 2:

def brute_force():
    guess = [None, None]
    for char in chars:
        guess[0] = char
        for char2 in chars:
            guess[1] = char2
            if ''.join(guess) == password:
                return ''.join(guess)

Finally I did the same for a password of length 3:

def brute_force():
    guess = [None, None, None]
    for char in chars:
        guess[0] = char
        for char2 in chars:
            guess[1] = char2
            for char3 in chars:
                guess[2] = char3
                if ''.join(guess) == password:
                    return ''.join(guess)

How could I generalize this for a variable called length which contains the integer value of the lenght of the password?

Solution:

You can use the following recursive function:

def brute_force(string, length, goal):
    if length == 1:
        for c in chars:
            if string + c == goal:
                return string + c
        return False
    for c in chars:
         s = brute_force(string + c, length - 1, goal)
         if s:
             return s
    return False

which you can call with syntax like:

>>> brute_force('', 3, 'bob')
'bob'
>>> brute_force('', 2, 'yo')
'yo'

Why does this work?

We always call each function with the three variables: string, length and goal. The variable string holds the current guess up to this point, so in the first example, string will be everything up to bob such as ab, bo etc.

The next variable length holds how many characters there are to go till the string is the right length.

The next variable goal is the correct password which we just pass through and is compare against.

In the main body of the function, we need to first check the case where length is 1. This is the case when we already have a string that is one off the length of the goal and we just want to check the final character. To check this last character, we just loop through the chars and for each one (c), we add (concatenate) that character to the end of the current string and compare that against our goal.

If it matches, then we return the result of that concatenation, otherwise we keep looping and check the next character. Eventually we reach the end of the for-loop and it is here that we return False. We return either the solution or False to indicate to the function which called us (the call above in the stack) that we found the right password.

We have now finished the case where length = 1 and now need to handle the other cases.

In these cases, the aim is to do exactly what we do in the case where length is one, but instead of comparing the result of the concatenation with the goal, we want to instead call the function again (I know it’s slightly confusing) with the result of this concatenation. You will notice though that we also have the other two variables to worry about: length and goal.

Well, to handle these, we just need to think what the next function needs to know. It already has the string as this was the result of concatenating the next character in the chars string and the length is just going to be one less as we just added one to the string through the concatenation and the goal is clearly going to be the same – we are still searching for the same password.

Now that we have called this function, it will run through subtracting one from the length at each of the subsequent calls it makes until it eventually reaches the case where length == 1. And we are at the easy case again and already know what to do!

So, after calling it, the function will return one of two things, either False indicating that the last node did not find the password (so this would occur in the case where something like ab reached the end in our search for bob so returned False after no solution was found), or, the call could return the actual solution.

Handling these cases is simple, if we got the actual solution, we just want to return that up the chain and if we got a fail (False), we just want to return False And that will indicate to the node above us that we did not succeed and tell it to continue its search.

So now, we just need to know how to call the function and that is simple, we just need to send in an empty string and a target length and goal value and let the recursion take place.

Note one last thing is that if you wanted this to be even neater, you could modify the function definition to:

def brute_force(length, goal, string=''):
    ...

and change the recursive call within. This way, you could call the function with something just like: brute_force(3, 'bob') and wouldn’t need to specify what string should start at. This is just something that you can add in if you want, but isn’t necessary for the function to work.