Find sequence number of a particular permutation in a lexicographical order.

PermutationNumber.java

package com.ffbit.permutation;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class PermutationNumber {
    private int permutation;
    private int expectedNumber;

    public PermutationNumber(int permutation, int expectedNumber) {
        this.permutation = permutation;
        this.expectedNumber = expectedNumber;
    }

    @Parameters
    public static Collection<Object[]> init() {
        return Arrays.asList(new Object[][] {
                { 12345678, 0 },
                { 12345687, 1 },
                { 53871462, 22299 },
                { 87654321, 40320 - 1 }
        });
    }

    @Test
    public void itShouldFindNumberOfAParticularPermutation() throws Exception {
        assertThat(findPermutationNumber(permutation), is(expectedNumber));
    }

    private int findPermutationNumber(int permutation) {
        int[] digits = getDigits(permutation);
        final int n = digits.length;
        int[] factorials = getFactorials(n);
        boolean[] usedDigits = new boolean[n];
        int permutationNumber = 0;

        for (int i = 0; i < n - 1; i++) {
            int digit = digits[i];
            int notUsedDigitsCount = 0;

            for (int j = 0; j < digit - 1; j++) {
                if (!usedDigits[j]) {
                    notUsedDigitsCount++;
                }
            }

            permutationNumber += factorials[n - i - 1] * notUsedDigitsCount;
            usedDigits[digit - 1] = true;
        }

        return permutationNumber;
    }

    @Test
    public void itShouldConverNumberToDigits() throws Exception {
        assertThat(getDigits(1234567), is(new int[] { 1, 2, 3, 4, 5, 6, 7 }));
    }

    private int[] getDigits(int n) {
        final int offset = '0';
        char[] chars = String.valueOf(n).toCharArray();
        int[] digits = new int[chars.length];

        for (int i = 0; i < chars.length; i++) {
            digits[i] = chars[i] - offset;
        }

        return digits;
    }

    @Test
    public void itShouldComputeFactorials() throws Exception {
        assertThat(getFactorials(4), is(new int[] { 1, 1, 2, 6 }));
    }

    private int[] getFactorials(int n) {
        int[] factorials = new int[n];
        factorials[0] = 1;

        for (int i = 1; i < n; i++) {
            factorials[i] = factorials[i - 1] * i;
        }

        return factorials;
    }

}