Permutation Coefficient

Table of Contents

Problem Statement

In this problem “Permutation Coefficient”, we need to find it when we are given the values of n & k.

Example

n = 5, k = 2

Explanation: This value of n P r is found using the formula of the permutation coefficient. nPr = n!/(n-r)!

Approach for finding Permutation Coefficient

To get to know about Permutation Coefficient. We must be aware of Permutation, it is nothing but any random sequence of numbers from 1 to n. So, now we know what is Permutation. But what is permutation coefficient?

It is nothing but number of ways to order r things out of n different things. So, to simplify what this means? This means that we had some n different elements and then we choose some r elements from it and now we need to find the ways of rearranging them. nPr denotes all the ways of doing. For example, 3P2 denotes ways to rearrange 2 elements chosen from a set of 3 different elements.

Permutation Coefficient

Permutation coefficient can also be easily understood as first we choose r elements out of n elements. So that is nCr then we rearrange r elements, so nPr = nCr * r! .

Recursive formula for the generation of Permutation Coefficient

P(n, k) = P(n-1, k) + k*P(n-1, k-1)

We can find the required answer using Dynamic Programming for the recursive formula to compute it efficiently.

Code

C++ code to get Permutation Coefficient

#include<bits/stdc++.h>
using namespace std;

int P[51][51];

//precomputePermutationCoefficient
void precomputePermutationCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0)
        P[i][j] = 1;
      else
        P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
    }
  }
}

int main()
{
  // precomputations being done for n = 50, you can change the value of n
  precomputePermutationCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the properties of permutation coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<P[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}

1
5 2

Java code to get Permutation Coefficient

import java.util.*;

class Main{
  static int P[][];

  // precompute permutation coefficient
  static void precomputePermutationCoefficients() 
  {

    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0) 
          P[i][j] = 1; 
        else
          P[i][j] = P[i - 1][j] + j * P[i - 1][j - 1]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    P = new int[51][51];
    // precomputations being done for n = 50, you can change the value of n
    precomputePermutationCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the properties of permutation coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(P[n][k]);		
      else
        System.out.println(0);
    }
  }
}

1
5 2

Complexity Analysis

Time Complexity

O(N^2 + Q), because to find our permutation coefficient we first need to precompute all the permutation coefficients which are necessary for the calculation of required answer. Thus the time complexity is polynomial. Here all the queries can be answered in O(1).

Space Complexity

O(N^2), because we have used a 2D array to store the precomputed result.

Optimized Approach for Permutation Coefficient

Since permutation coefficient is nothing but multiplication of numbers from n to n-k+1. We can simply calculate nPk in O(1) space and O(N) time.

Code

C++ code for optimized approach

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,k;cin>>n>>k;
  int P = 1;
  for(int i=n;i>=(n-k+1);i--)
    P*=i;
  cout<<P<<endl;
}

5 2

Java code for optimized approach

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int P = 1;
    for(int i=n;i>=(n-k+1);i--)
      P*=i;
    System.out.println(P);
  }
}

5 2