Reversing function to obtain the lexicographic index of a given permutation

Question

I'm working on a Python3 code challenge where a message is encoded on or decoded from the shuffling order of a 52-card standard playing deck. I have already found how to encode the message, but I am having difficulty reversing the function to get a message from a given shuffling order. I have a function that finds a lexicographic permutation of a list of cards based on its index. I need one now that takes a permutation from a list of cards and outputs its index. I have some ideas, but I'm not as good at number theory as I should be. I have put some comments with my ideas.

deck = ["AC", "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "TC", "JC", "QC", "KC",
        "AD", "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "TD", "JD", "QD", "KD",
        "AH", "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "TH", "JH", "QH", "KH",
        "AS", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "TS", "JS", "QS", "KS",]

def get_nth_permutation( p_index, in_list, out_list=[] ):

    if p_index >= factorial( len(in_list) ): return []
    if not in_list: return out_list

    f = factorial( len(in_list)-1 )
    index = p_index / f # p_index * f
    remainder = p_index % f # pow(p_index, -1, f) - reverse modulo?
    # reverse divmod by adding index + remainder in each step to increase p_index?
    out_list.append( in_list[int(index)] )
    del in_list[int(index)]

    if not remainder: # function should end when out_list + in_list matches deck
        return out_list + in_list # return p_index
        
    else: #keep recursion if possible
        return get_nth_permutation( remainder, in_list, out_list ) 

Any help is appreciated. It doesn't even have to be code, even a pseudocode explanation or some next steps is better than where I am right now.

Answer 1

You would take the index of the first entry and multiply it by the number of permutations possible for the rest of the list (without that first entry). Repeat this logic for the next entries of the list.

Here is an implementation:

def get_permutation_index(ordered, perm):
    ordered = ordered[:]  # Get a copy so we don't mutate the original list
    result = 0
    for card in perm:
        i = ordered.index(card)
        ordered.pop(i)
        result += i * factorial(len(ordered))
    return result

Remarks

• The above function returns an index that is 0-based, just like your function will return the first permutation when you pass 0 for p_index, and the second when you pass 1. If the purpose was to start counting at 1 (as _nth_ in your function name suggests), you need to adapt both functions.

• Your function empties the given in_list. This means that if you call it again with deck as argument (or the above function), you'll be passing an empty list. It would be better if your function would not mutate the original list.

• Giving [] as a default value has side effects for subsequent calls that omit this parameter. See The Mutable Default Argument in Python. I would suggest to not have this argument, and instead make a recursive generator from which you build the list to return.

• Don't use the / division operator and then int(). Instead use the integer division operator: //

Here is your function with those adaptations:

def get_nth_permutation( p_index, in_list):  # Don't use mutable default
    in_list = in_list[:]  # Avoid mutating the original list
    
    def recur(p_index):
        if p_index >= factorial( len(in_list) ) or not in_list: 
            return
        if not p_index: 
            yield from in_list
            return
        
        f = factorial( len(in_list)-1 )
        index = p_index // f  # Don't use floating point division
        remainder = p_index % f
        yield in_list[index]
        del in_list[index]
        yield from recur(remainder)

    return list(recur(p_index))