leetcode 3109 solution

leetcode3109.py

"""
This is the solution for: https://leetcode.com/problems/find-the-index-of-permutation/description/
It is not available without premium though

Given an array perm of length n which is a permutation of [1, 2, ..., n], return the index of perm in the lexicographically sorted array of all of the permutations of [1, 2, ..., n].

Since the answer may be very large, return it modulo 10^9 + 7. 

Example 1:

Input: perm = [1,2]

Output: 0

Explanation:

There are only two permutations in the following order:

[1,2], [2,1]

And [1,2] is at index 0.

Example 2:

Input: perm = [3,1,2]

Output: 4

Explanation:

There are only six permutations in the following order:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

And [3,1,2] is at index 4.

n <= 10^5
"""

"""
[3,1,2]

N! permutations

[1,2,3], 
[1,3,2], 
[2,1,3], 
[2,3,1], 
[3,1,2], 
[3,2,1]

each number as first number is repeated n!/n == (n-1)! times

skip (num-1)*((n-1)!)
skip 4
left with
[3,1,2], 
[3,2,1]

[1,2], 
[2,1]


new example
[2,3,1]
remove 2, [3,1] replace 3 with 2, [2,1]

remove the first element
we replace all elements higher than first element with element-1

[2,3,4,1]
[3,4,1] -> [2,3,1]
[3,1] -> [2,1]
// [1] -> [1]

for every removed element we decrement every higher element by 1

when removing an element we find how many elements lower than it were already removed and decrease it by this number.

"""


"""
[3,1,2]
index+=(3-1)*(step=2)=4
[1,2]
index+=(1-1)*(step=1)=0
"""
from typing import *
from math import *
from sortedcontainers import SortedList
from itertools import permutations

MOD = 10**9+7

class Solution:
    def getPermutationIndex(self, perm: List[int]) -> int:

      factorials = [1, 1]
      for i in range(2, len(perm)):
        factorials.append((factorials[i-1]*i) % MOD)

      perm_index = 0
      removed = SortedList([])

      for n in range(len(perm), 1, -1):
        num = perm[len(perm)-n]
        step = factorials[n-1]
        count_lower = removed.bisect(num)
        actual_num = num - count_lower
        perm_index += (actual_num-1) * step
        perm_index %= MOD
        removed.add(num)
      
      return perm_index

solution = Solution()
assert(solution.getPermutationIndex([2,1,3,4])==6)
assert(solution.getPermutationIndex([1,2,3])==0) 
assert(solution.getPermutationIndex([1,3,2])==1) 
assert(solution.getPermutationIndex([2,1,3])==2) 
assert(solution.getPermutationIndex([2,3,1])==3) 
assert(solution.getPermutationIndex([3,1,2])==4) 
assert(solution.getPermutationIndex([3,2,1])==5)

for n in range(4, 9):
   for i, perm in enumerate(permutations(range(1, n+1))):
      assert(solution.getPermutationIndex(list(perm))==i)