Permutation index Python Here is my Python code for finding the permutation index of a given digits and a target number. And by permutation index I mean, for example, given digits [1, 2, 3, 4]. find the index of 3124, meaning the position of 3124 in all permutations. This code finds that. However I have suspicions about it efficiency and implementation. Please review my code.

def perm_ind(numbers, target, length):
    """
    Finding the position of a single permutation in all permutations.
    Using the mathematic formula. 
    """

    ranks = sorted(numbers) # For keeping the index even after some numbers are placed and removed.
    ind = 0
    for step in reversed(xrange(length)):

        num = (target / 10 ** step) # These two lines are used to get
        target %= 10 ** step        # the left-most digit in each iteration

        times = ranks.index(num) # Find the rank of the currect digit.

        ind += factorial(length - 1) * times # Add to result
        ranks.remove(num) # Remove the used(Placed) number
        length -= 1 # Decrease length

    return ind

# Example usages
print perm_ind([1, 2, 3], 123, 3)
print perm_ind([1, 2, 3], 132, 3)
print perm_ind([1, 2, 3], 213, 3)
Interface


The parameters passed to the function are not orthogonal; they are subject to a number of restrictions, such as


length == len(numbers)
length == len(str(target))
target is composed of precisely the elements of numbers



If any restriction is violated, the function fails with an exception, or produces the wrong result. You may want to validate the input, or revise the interface to infer as much as possible from as little as necessary.

For example, it is reasonable to assume that length is len(numbers), and don't pass it at all. It is also reasonable to assume that target is well formed, and infer the alphabet from it.


By passing target as an integer you severely restrict the utility of a function. I highly recommend to pass it as a list of (comparable) elements.

Efficiency

First obvious inefficiency is recalculation of factorial, which drives the complexity quadratic by length. I recommend precompute factor = factorial(length) before the loop, and do

    factor /= length
    ind += factor * times
    length -= 1


to reduce the complexity to linear.

Second, extraction of leading digit also involves heavyweight computations. Even if the target is passed as integer, you'd be better off by converting it to an iterable, e.g.

    target = str(target)


and access individual digits positionally. And let me reiterate, it is better to pass target as iterable in the first place.