Introduction

The index of a permutation in lexicographically sorted order can be computed without generating all permutations. The usual idea is to count how many valid permutations would appear before the current prefix. For strings with unique letters, that is a factorial-number-system problem. For strings with repeated letters, you also divide by duplicate-count factorials.

Start with the lexicographic counting idea

Suppose the target string is bac. In sorted order, every permutation starting with a comes before every permutation starting with b. So before you reach bac, you count all permutations that begin with smaller available letters at each position.

That gives a clean pattern:

1. look at the current character
2. count unused smaller characters that could appear here
3. add the number of permutations each such choice would generate
4. mark the current character as used and continue

Unique-character version

For strings with all distinct characters, the number of permutations contributed by a smaller character at position i is (n - i - 1)!.

1from math import factorial
2
3
4def permutation_rank_unique(s: str) -> int:
5    chars = sorted(s)
6    rank = 0
7    n = len(s)
8
9    for i, ch in enumerate(s):
10        index = chars.index(ch)
11        rank += index * factorial(n - i - 1)
12        chars.pop(index)
13
14    return rank
15
16
17print(permutation_rank_unique("abc"))
18print(permutation_rank_unique("bac"))
19print(permutation_rank_unique("cba"))

This returns a zero-based rank.

Repeated characters need duplicate adjustment

If the string contains duplicate letters, naive factorial counting overcounts permutations because swapping identical letters does not create a new distinct arrangement.

For a multiset of remaining letters, the number of distinct permutations is:

• total remaining factorial
• divided by the factorial of each character count

That is the key correction.

Rank algorithm that handles duplicates

1from collections import Counter
2from math import factorial
3
4
5def count_permutations(counts: Counter) -> int:
6    total = sum(counts.values())
7    result = factorial(total)
8    for count in counts.values():
9        result //= factorial(count)
10    return result
11
12
13def permutation_rank(s: str) -> int:
14    counts = Counter(s)
15    rank = 0
16
17    for ch in s:
18        for smaller in sorted(c for c in counts if c < ch and counts[c] > 0):
19            counts[smaller] -= 1
20            rank += count_permutations(counts)
21            counts[smaller] += 1
22
23        counts[ch] -= 1
24        if counts[ch] == 0:
25            del counts[ch]
26
27    return rank
28
29
30print(permutation_rank("AAB"))
31print(permutation_rank("ABA"))
32print(permutation_rank("BAA"))

This version correctly handles repeated letters and still returns a zero-based rank.

Convert to one-based index if needed

Some interview problems or math texts want the first permutation to have index 1 rather than 0. In that case, just add 1 at the end.

print(permutation_rank("BAC") + 1)

Always state which convention you are using, because off-by-one confusion is very common in this problem.

Why generating all permutations is the wrong approach

A brute-force approach that lists every permutation, sorts them, and then searches for the target is wildly inefficient for all but tiny strings. The number of permutations grows factorially, so even medium-length strings become impractical.

The counting method is better because it computes the rank directly from combinatorics.

Common Pitfalls

• Generating all permutations instead of counting lexicographic blocks directly.
• Forgetting that repeated characters require division by duplicate factorials.
• Mixing zero-based and one-based indexing without stating which one is returned.
• Reusing the unique-character formula on strings that contain duplicates.
• Sorting the whole permutation list when the rank can be computed incrementally.

Summary

• Compute permutation rank by counting how many lexicographically smaller prefixes are possible at each position.
• For unique characters, the count is based on factorial blocks.
• For duplicate characters, divide by duplicate-count factorials to avoid overcounting.
• Return zero-based or one-based rank deliberately and document the choice.
• Direct combinatorial counting is far better than generating every permutation.