Python, permutation to permuation-index function

Off the top of my head I came up with the following, didn't test it thoroughly.

from math import factorial
elements = list(range(4))
permutation = (3, 2, 1, 0)
index = 0
nf = factorial(len(elements))

for n in permutation:
    nf //= len(elements)
    index += elements.index(n) * nf
    elements.remove(n)

print(index)

EDIT: replaced nf /= len(elements) with nf //= len(elements)

I suppose this is a challenge, so here is my (recursive) answer:

import math
import itertools

def get_index(l):
    # In a real function, there should be more tests to validate that the input is valid, e.g. len(l)>0
    # Terminal case
    if len(l)==1:
        return 0

    # Number of possible permutations starting with l[0]
    span = math.factorial(len(l)-1)

    # Slightly modifying l[1:] to use the function recursively
    new_l = [ val if val < l[0] else val-1 for val in l[1:] ]

    # Actual solution
    return get_index(new_l) + span*l[0]


get_index((0,1,2,3))
# 0
get_index((0,2,3,1))
# 3
get_index((3,2,1,0))
# 23
get_index((4,2,0,1,5,3))
# 529
list(itertools.permutations((0,1,2,3,4,5))).index((4,2,0,1,5,3))
# 529

You need to write your own function. Something like this would work

import math

def perm_loc(P):

    N = len(P)
    assert set(P) == set(range(N))

    def rec(perm):
        nums = set(perm)
        if not perm:
            return 0
        else:
            sub_res = rec(perm[1:])                  # Result for tail of permutation
            sub_size = math.factorial(len(nums) - 1) # How many tail permutations exist
            sub_index = sorted(nums).index(perm[0])  # Location of first element in permutaiotn
                                                     # in the sorted list of number
            return sub_index * sub_size + sub_res

    return rec(P)

The function that does all the work is rec, with perm_loc just serving as a wrapper around it. Note that this algorithm is based on the nature of the permutation algorithm that itertools.permutation happens to use.

The following code tests the above function. First on your sample, and then on all permutations of range(7):

print perm_loc([0,2,3,1]) # Print the result from the example

import itertools

def test(N):
    correct = 0
    perms = list(itertools.permutations(range(N)))
    for (i, p) in enumerate(perms):
        pl = perm_loc(p)
        if i == pl:
            correct += 1
        else:
            print ":: Incorrect", p, perms.index(p), perm_loc(N, p)
    print ":: Found %d correct results" % correct

test(7) # Test on all permutations of range(7)

from math import factorial

def perm_to_permidx(perm):
    # Extract info
    n = len(perm)
    elements = range(n)
    # "Gone"s will be the elements of the given perm
    gones = []
    # According to each number in perm, we add the repsective offsets
    offset = 0
    for i, num in enumerate(perm[:-1], start=1):
        idx = num - sum(num > gone for gone in gones)
        offset += idx * factorial(n - i)
        gones.append(num)
    return offset

the_perm = (0, 2, 3, 1)
print(perm_to_permidx(the_perm))
# 3

Explanation: All permutations of a given range can be considered as a groups of permutations. So, for example, for the permutations of 0, 1, 2, 3 we first "fix" 0 and permute rest, then fix 1 and permute rest, and so on. Once we fix a number, the rest is again permutations; so we again fix a number at a time from the remaining numbers and permute the rest. This goes on till we are left with one number only. Every level of fixing has a corresponding (n-i)! permutations.

So this code finds the "offsets" for each level of permutation. The offset corresonds to where the given permutation starts when we fix numbers of perm in order. For the given example of (0, 2, 3, 1), we first look at the first number in the given perm which is 0, and figure the offset as 0. Then this goes to gones list (we will see its usage). Then, at the next level of permutation we see 2 as the fixing number. To calculate the offset for this, we need the "order" of this 2 among the remaining three numbers. This is where gones come into play; if an already-fixed and considered number (in this case 0) is less than the current fixer, we subtract 1 to find the new order. Then offset is calculated and accumulated. For the next number 3, the new order is 3 - (1 + 1) = 1 because both previous fixers 0 and 2 are at the "left" of 3.

This goes on till the last number of the given perm since there is no need to look at it; it will have been determined anyway.