Permutation index Python

Question

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)

Answer 1

• Interface

  1. 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.

  2. 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.