Modular Permutation

and program to find the Modular Permutation using Modular factorial Array and Modular Multiplicative inverse in Rust

Introduction

In many problems, it becomes unfeasible to calculate Permutation using traditional data types like i64 or even i128 due to overflow. The largest integer data type in rust, u128 can hold the number upto order of 10³⁸. But Permutations grows pretty fast with n and r. For example, ¹⁰⁰P₁₀₀ is approximately is 9.33 × 10¹⁵⁷

So, it becomes unfeasible from competitive programming point of view to compute exact values using C / C++ / Rust etc. So, in most programming contest, we have to find the answer modulo with respect to given number, generally 10⁹ + 7 or 1000000007 is used because It is safe prime number.

Hence, we will discuss how to find Modular Permutation or permutation of a large number with respect to a given number using Modular factorial Array and Modular Multiplicative inverse in Rust.

Single Permutation

When we have to find the value of 1 ⁿP_r, we can just find the modular permutation by using modular multiplication and multiplying numbers from n-r+1 to n, inclusive.

Note: This would take linear time complexity for each permutation. So, this is efficient when there are fewer of queries ( When there are less than log(n) queries to be precise.)

Here is code for above implementation.

fn modular_permutation(n: i128, r: i128, p:i128) -> i128{
    // Take Answer to be 1
    let mut ans = 1;

    // nPr = n! / (n-r)! = (n-r+1) × (n-r+2) × .... × n
    for i in (n-r+1)..(n+1) {
        ans *= i;

        // Division and Modulo are expensive for cpu
        // So, we find modulo if answer is greater than or equal to p
        // It can never become p though, else, answer will become 0
        if ans>=p {
            ans = ans%p;
        }
    }

    return ans;
}

With Driver Code

fn modular_permutation(n: i128, r: i128, p:i128) -> i128{
    // Take Answer to be 1
    let mut ans = 1;

    // nPr = n! / (n-r)! = (n-r+1) × (n-r+2) × .... × n
    for i in (n-r+1)..(n+1) {
        ans *= i;

        // Division and Modulo are expensive for cpu
        // So, we find modulo if answer is greater than or equal to p
        // It can never become p though, else, answer will become 0
        if ans>=p {
            ans = ans%p;
        }
    }

    return ans;
}

// Driver code

use std::io::stdin;
fn take_int() -> i128 {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

pub fn main() {
    // Take values of n, r and p
    let n = take_int();
    let r = take_int();
    let p = take_int();
    println!("{}", modular_permutation(n, r, p));
}

Input

100
50
1000000007

Output

505671657

Time Complexity : O( n )
Space Complexity : O( 1 )

Efficient Approach

When we have to find large number of modular permutations, say 10⁵ or 10⁶ permutations and n can also range up to 10⁵ or 10⁶, we can clearly see that above approach will result into TLE (Time Limit Exceeded) in Competitive Programming contests.

So, we have to find Modular Permutation in least time for each test case.

The idea is to first generate a Modular Factorial Array and then find the number of permutations using equation

ⁿP_r = n! / (n-r)!

Using Modular Arithmetic, this equation becomes

(ⁿ P _r) mod p = ((n!) mod p * (n-r)! ^-1 mod p) mod p

To find the number of permutations.

The implementation using this approach is.

fn modular_permutation(n: usize, r: usize, p:usize, factorial_array:&Vec<usize>) -> usize{
    return (factorial_array[n] * mod_inverse(factorial_array[n - r], p)) % p;
}

With driver code

fn modular_permutation(n: usize, r: usize, p:usize, factorial_array:&Vec<usize>) -> usize{
    return (factorial_array[n] * mod_inverse(factorial_array[n - r], p)) % p;
}

// Driver code

use std::io::stdin;
fn take_int() -> usize {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}


fn generate_factorial_array(max_number : usize, divisor : usize) -> Vec<usize>{
    let mut factorial_array : Vec<usize> = vec![1; max_number+1];
    for i in 2..(max_number + 1) {
        factorial_array[i] = (factorial_array[i-1] * i) % divisor; }
    return factorial_array;
}

fn modular_exponent(mut n:usize ,mut x:usize , p:usize) -> usize{
    let mut ans = 1;
    if x<=0 { return 1; }
    loop { if x==1 { return (ans * n) % p; }
        if x&1==0 { n=( n * n ) % p; x>>=1;continue; }
        else { ans = (ans*n) % p; x-=1; }
    }
}

fn mod_inverse (n:usize, p:usize) -> usize{
    return modular_exponent(n, p-2, p);
}

pub fn main() {
    // Take values of n, r and p
    let n = take_int();
    let r = take_int();
    let p = take_int();
    // Contains factorial of all numbers from 1 to 10^6, modulo 10^9 + 7
    let factorial_array = generate_factorial_array(1_000_000, 1_000_000_007);
    println!("{}", modular_permutation(n, r, p, &factorial_array));
}

Input

100
50
1000000007

Output

505671657

Time Complexity : O( nlog(n) )
Space Complexity : O( n )

Note: Although the time complexity is higher in this approach, it will be very less for higher number of queries. For example, if we have n queries of ⁿP_r, the time taken by this approach will still be O( nlog(n) ), whereas earlier approach will take O( n² ) time. So, this is efficient only when there are higher number of queries.

Summary

Finding number of possible Permutations is one of the standard problems in Combinatorics. But as we know, it grows pretty fast, and it becomes necessary to compute modulo of number of Permutations in many problems.

So, in this article, we saw how to find modular Permutation using Modular factorial Array and Modular Multiplicative inverse in Rust.

Here is code for easy access

fn modular_exponent(mut n:usize ,mut x:usize , p:usize) -> usize{
    let mut ans = 1;
    if x<=0 { return 1; }
    loop { if x==1 { return (ans * n) % p; }
        if x&1==0 { n=( n * n ) % p; x>>=1;continue; }
        else { ans = (ans*n) % p; x-=1; }
    }
}

fn mod_inverse (n:usize, p:usize) -> usize{
    return modular_exponent(n, p-2, p);
}

// Here is the function
fn modular_permutation(n: usize, r: usize, p:usize, factorial_array:&Vec<usize>) -> usize{
    return (factorial_array[n] * mod_inverse(factorial_array[n - r], p)) % p;
}