Permutation Rank

Problem

Find the rank of a number digits in the lexicographic order of its permutations

Examples

Example 1

Input: digits = [3, 1, 2]
Output: 5
Explanation: The sorted permutation list is [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. The rank of [3, 1, 2] is 5 (1-based).

Solution

Method 1 - Brute Force

The brute force approach involves generating every possible permutation of the input digits, sorting all these permutations in lexicographic order, and then finding the position (rank) of the original number in this sorted list. While this method is easy to understand, it is highly inefficient because the number of permutations grows factorially with the number of digits, making it impractical for large inputs.

Method 2 - Using Maths

This method uses combinatorial mathematics to efficiently determine the rank of a given permutation without generating all possible permutations.

Take the number X = 415, represented as the digits [4, 5, 1]. Start by assuming the rank is 1.

For each digit, calculate how many permutations can be formed by placing a smaller digit in the current position and arranging the remaining digits. For example:

• At position 0 (digit 4), there is one smaller digit (1). Placing 1 at position 0 allows for 2! arrangements of the remaining digits, so rank += 2 (rank = 3).
• Move to position 1 (digit 5). There is one smaller digit (1) among the remaining digits. Placing 1 at position 1 allows for 1! arrangement, so rank += 1 (rank = 4).
• At position 2 (digit 1), there are no smaller digits left, so no additional permutations are added.

Repeat this process for each position. The final rank is the sum of all such contributions, plus the initial rank of 1.

The provided code implements this logic. It runs in O(n^2) time because counting smaller digits to the right of each position is O(n^2). This can be improved to O(n log n) using inversion counting or advanced data structures. For more details, see: [Count Inversions - Count Smaller on Right](count-inversions-count-smaller-on-right).

Code

C++

#include <vector>

std::vector<int> smallerCountOnRight(const std::vector<int>& digits) {
	std::vector<int> smaller(digits.size(), 0);
	for (size_t i = 0; i < digits.size(); ++i) {
		for (size_t j = i + 1; j < digits.size(); ++j) {
			if (digits[j] < digits[i]) {
				smaller[i]++;
			}
		}
	}
	return smaller;
}

int permRank(const std::vector<int>& digits) {
	std::vector<int> smallerCount = smallerCountOnRight(digits);
	std::vector<int> factorial(digits.size() + 1, 1);
	for (size_t i = 1; i <= digits.size(); ++i) {
		factorial[i] = i * factorial[i - 1];
	}
	int rank = 1;
	for (size_t i = 0; i < digits.size(); ++i) {
		rank += smallerCount[i] * factorial[digits.size() - i - 1];
	}
	return rank;
}

Java

public static int[] smallerCountOnRight(final int[] digits) {
	int[] smaller = new int[digits.length];
	// For each digit, count how many digits to its right are smaller
	for (int i = 0; i < digits.length; i++) {
		for (int j = i + 1; j < digits.length; j++) {
			if (digits[j] < digits[i]) {
				smaller[i]++;
			}
		}
	}
	return smaller;
}

public static int permRank(final int[] digits) {
	int[] smallerCount = smallerCountOnRight(digits);
	int[] factorial = new int[digits.length + 1];
	factorial[0] = 1;
	// Compute factorials up to n
	for (int i = 1; i <= digits.length; i++) {
		factorial[i] = i * factorial[i - 1];
	}
	int rank = 1;
	for (int i = 0; i < digits.length; i++) {
		rank += smallerCount[i] * factorial[digits.length - i - 1];
	}
	return rank;
}

Python

from typing import List

def smaller_count_on_right(digits: List[int]) -> List[int]:
	smaller = [0] * len(digits)
	for i in range(len(digits)):
		for j in range(i + 1, len(digits)):
			if digits[j] < digits[i]:
				smaller[i] += 1
	return smaller

def perm_rank(digits: List[int]) -> int:
	smaller_count = smaller_count_on_right(digits)
	factorial = [1] * (len(digits) + 1)
	for i in range(1, len(digits) + 1):
		factorial[i] = i * factorial[i - 1]
	rank = 1
	for i in range(len(digits)):
		rank += smaller_count[i] * factorial[len(digits) - i - 1]
	return rank

Complexity

⏰ Time complexity: O(n^2) — For each digit, we count smaller digits to its right, and compute factorials. 🧺 Space complexity: O(n) — Uses extra space for the count and factorial arrays.