Permutation Index排列序号

lintcode

Problem Statement

Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1. Example

Given [1,2,4], return 1.

解题思路

假设一个整数有n位数字组成，则

• 左边第一位数字(数组索引是0)的排列权重为(n-1)!
• 左边第二位数字(数组索引是1)的排列权重为(n-2)!
• 左边第i+1位数字(数组索引是i)的排列权重为(n-i-1)!
• 最右边数字(数组索引是n-1)的排列权重为0!

用$rank_{i}$表示数组索引为i+1到n-1的数字小于s索引为i的数字的个数，那么一个排列的序号可以用下面的公式计算：

$\sum_{i=0}^{n-1}rank_{i}*(n-i-1)!$

对应的Java实现

 public long permutationIndex(int[] A) {
    if (A == null || A.length == 0) return 0L;

    long index = 1, fact = 1;
    for (int i = A.length - 1; i >= 0; i--) {
        //get rank in every iteration
        int rank = 0;
        for (int j = i + 1; j < A.length; j++) {
            if (A[i] > A[j]) rank++;
        }

        index += rank * fact;
        fact *= (A.length - i);
    }

    return index;
}

一些数学公式的TEX表示

$-b \pm \sqrt{b^2 - 4ac} \over 2a$

$\cos (2\theta) = \cos^2 \theta - \sin^2 \theta$

$m_{2} k_{n+1}k = \frac{n(n+1)}{2}$

References

1 Permutation Index

2 Permutation Sequence