Tutorialspoint.dev

Permutation Coefficient

Permutation refers to the process of arranging all the members of a given set to form a sequence. The number of permutations on a set of n elements is given by n! , where “!” represents factorial.
The Permutation Coefficient represented by P(n, k) is used to represent the number of ways to obtain an ordered subset having k elements from a set of n elements.

Mathematically it’s given as:
permu

Image Source : Wiki

Examples :

P(10, 2) = 90
P(10, 3) = 720
P(10, 0) = 1
P(10, 1) = 10

The coefficient can also be computed recursively using the below recursive formula:



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

If we observe closely, we can analyze that the problem has overlapping substructure, hence we can apply dynamic programming here. Below is a program implementing the same idea.

C

// A Dynamic Programming based 
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient
#include<bits/stdc++.h>
  
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff(int n, int k)
{
    int P[n + 1][k + 1];
  
    // Caculate value of Permutation 
    // Coefficient in bottom up manner
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= std::min(i, k); j++)
        {
            // Base Cases
            if (j == 0)
                P[i][j] = 1;
  
            // Calculate value using
            // previosly stored values
            else
                P[i][j] = P[i - 1][j] + 
                          (j * P[i - 1][j - 1]);
  
            // This step is important
            // as P(i,j)=0 for j>i
            P[i][j + 1] = 0;
        }
    }
    return P[n][k];
}
  
// Driver Code
int main()
{
    int n = 10, k = 2;
    printf("Value of P(%d, %d) is %d ",
            n, k, permutationCoeff(n, k));
    return 0;
}

Java

// Java code for Dynamic Programming based 
// solution that uses table P[][] to 
// calculate the Permutation Coefficient
import java.io.*;
import java.math.*;
  
class GFG 
{
      
    // Returns value of Permutation 
    // Coefficient P(n, k)
    static int permutationCoeff(int n, 
                                int k)
    {
        int P[][] = new int[n + 2][k + 2];
      
        // Caculate value of Permutation 
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0
                 j <= Math.min(i, k); 
                 j++)
            {
                // Base Cases
                if (j == 0)
                    P[i][j] = 1;
      
                // Calculate value using previosly 
                // stored values
                else
                    P[i][j] = P[i - 1][j] + 
                               (j * P[i - 1][j - 1]);
      
                // This step is important 
                // as P(i,j)=0 for j>i
                P[i][j + 1] = 0;
            }
        }
        return P[n][k];
    }
      
    // Driver Code
    public static void main(String args[])
    {
        int n = 10, k = 2;
        System.out.println("Value of P( " + n + ","+ k +")"
                           " is " + permutationCoeff(n, k) );
    }
}
  
// This code is contributed by Nikita Tiwari.

Python3

# A Dynamic Programming based
# solution that uses
# table P[][] to calculate the
# Permutation Coefficient
  
# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):
  
    P = [[0 for i in range(k + 1)] 
            for j in range(n + 1)]
  
    # Calculate value of Permutation
    # Coefficient in
    # bottom up manner
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
  
            # Base cases
            if (j == 0):
                P[i][j] = 1
  
            # Calculate value using 
            # previously stored values
            else:
                P[i][j] = P[i - 1][j] + (
                           j * P[i - 1][j - 1])
  
            # This step is important 
            # as P(i, j) = 0 for j>i
            if (j < k):
                P[i][j + 1] = 0
    return P[n][k]
  
# Driver Code
n = 10
k = 2
print("Value fo P(", n, ", ", k, ") is ",
       permutationCoeff(n, k), sep = "")
  
# This code is contributed by Soumen Ghosh.

C#

// C# code for Dynamic Programming based 
// solution that uses table P[][] to 
// calculate the Permutation Coefficient
using System;
  
class GFG 
{
      
    // Returns value of Permutation 
    // Coefficient P(n, k)
    static int permutationCoeff(int n, 
                                int k)
    {
        int [,]P = new int[n + 2,k + 2];
      
        // Caculate value of Permutation 
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; 
                j <= Math.Min(i, k); 
                j++)
            {
                // Base Cases
                if (j == 0)
                    P[i,j] = 1;
      
                // Calculate value using previosly 
                // stored values
                else
                    P[i,j] = P[i - 1,j] + 
                            (j * P[i - 1,j - 1]);
      
                // This step is important 
                // as P(i,j)=0 for j>i
                P[i,j + 1] = 0;
            }
        }
        return P[n,k];
    }
      
    // Driver Code
    public static void Main()
    {
        int n = 10, k = 2;
        Console.WriteLine("Value of P( " + n + 
                        ","+ k +")" + " is "
                        permutationCoeff(n, k) );
    }
}
  
// This code is contributed by anuj_67..

PHP

<?php
// A Dynamic Programming based 
// solution that uses table P[][]
// to calculate the Permutation
// Coefficient
  
// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff( $n, $k)
{
    $P = array(array());
  
    // Caculate value of Permutation 
    // Coefficient in bottom up manner
    for($i = 0; $i <= $n; $i++)
    {
        for($j = 0; $j <= min($i, $k); $j++)
        {
              
            // Base Cases
            if ($j == 0)
                $P[$i][$j] = 1;
  
            // Calculate value using
            // previosly stored values
            else
                $P[$i][$j] = $P[$i - 1][$j] + 
                            ($j * $P[$i - 1][$j - 1]);
  
            // This step is important
            // as P(i,j)=0 for j>i
            $P[$i][$j + 1] = 0;
        }
    }
    return $P[$n][$k];
}
  
    // Driver Code
    $n = 10; $k = 2;
    echo "Value of P(",$n," ,",$k,") is ",
               permutationCoeff($n, $k);
  
// This code is contributed by anuj_67.
?>


Output :

Value of P(10, 2) is 90 

Here as we can see the time complexity is O(n*k) and space complexity is O(n*k) as the program uses an auxiliary matrix to store the result.

Can we do it in O(n) time ?
Let us suppose we maintain a single 1D array to compute the factorials up to n. We can use computed factorial value and apply the formula P(n, k) = n! / (n-k)!. Below is a program illustrating the same concept.

C

// A O(n) solution that uses 
// table fact[] to calculate 
// the Permutation Coefficient
#include<bits/stdc++.h>
  
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff(int n, int k)
{
    int fact[n + 1];
  
    // base case
    fact[0] = 1;
  
    // Caculate value 
    // factorials up to n
    for (int i = 1; i <= n; i++)
        fact[i] = i * fact[i - 1];
  
    // P(n,k) = n! / (n - k)!
    return fact[n] / fact[n - k];
}
  
// Driver Code
int main()
{
    int n = 10, k = 2;
    printf ("Value of P(%d, %d) is %d ",
             n, k, permutationCoeff(n, k) );
    return 0;
}

Java

// A O(n) solution that uses 
// table fact[] to calculate 
// the Permutation Coefficient
import java .io.*;
  
public class GFG {
      
    // Returns value of Permutation
    // Coefficient P(n, k)
    static int permutationCoeff(int n, 
                                int k)
    {
        int []fact = new int[n+1];
      
        // base case
        fact[0] = 1;
      
        // Caculate value 
        // factorials up to n
        for (int i = 1; i <= n; i++)
            fact[i] = i * fact[i - 1];
      
        // P(n,k) = n! / (n - k)!
        return fact[n] / fact[n - k];
    }
      
    // Driver Code
    static public void main (String[] args)
    {
        int n = 10, k = 2;
        System.out.println("Value of"
        + " P( " + n + ", " + k + ") is "
        + permutationCoeff(n, k) );
    }
}
  
// This code is contributed by anuj_67.

Python3

# A O(n) solution that uses 
# table fact[] to calculate 
# the Permutation Coefficient
  
# Returns value of Permutation
# Coefficient P(n, k)
def permutationCoeff(n, k):
    fact = [0 for i in range(n + 1)]
  
    # base case
    fact[0] = 1
  
    # Calculate value 
    # factorials up to n
    for i in range(1, n + 1):
        fact[i] = i * fact[i - 1]
  
    # P(n, k) = n!/(n-k)!
    return int(fact[n] / fact[n - k])
  
# Driver Code
n = 10
k = 2
print("Value of P(", n, ", ", k, ") is ",
        permutationCoeff(n, k), sep = "")
  
# This code is contributed
# by Soumen Ghosh

C#

// A O(n) solution that uses 
// table fact[] to calculate 
// the Permutation Coefficient
using System;
  
public class GFG {
      
    // Returns value of Permutation
    // Coefficient P(n, k)
    static int permutationCoeff(int n, 
                                int k)
    {
        int []fact = new int[n+1];
      
        // base case
        fact[0] = 1;
      
        // Caculate value 
        // factorials up to n
        for (int i = 1; i <= n; i++)
            fact[i] = i * fact[i - 1];
      
        // P(n,k) = n! / (n - k)!
        return fact[n] / fact[n - k];
    }
      
    // Driver Code
    static public void Main ()
    {
        int n = 10, k = 2;
        Console.WriteLine("Value of"
        + " P( " + n + ", " + k + ") is "
         + permutationCoeff(n, k) );
    }
}
  
// This code is contributed by anuj_67.

PHP

<?php
// A O(n) Solution that 
// uses table fact[] to 
// calculate the Permutation 
// Coefficient
  
// Returns value of Permutation
// Coefficient P(n, k)
function permutationCoeff($n, $k)
{
    $fact = array();
  
    // base case
    $fact[0] = 1;
  
    // Calculate value 
    // factorials up to n
    for ($i = 1; $i <= $n; $i++)
        $fact[$i] = $i * $fact[$i - 1];
  
    // P(n,k)= n!/(n-k)!
    return $fact[$n] / $fact[$n - $k];
}
  
    // Driver Code
    $n = 10;
    $k = 2;
    echo"Value of P(",$n," ", $k,") is ",
            permutationCoeff($n, $k) ;
              
// This code is contributed by anuj_67.             
?>


Output :

Value of P(10, 2) is 90 

A O(n) time and O(1) Extra Space Solution

C

// A O(n) time and O(1) extra
// space solution to calculate
// the Permutation Coefficient
#include <iostream>
using namespace std;
  
int PermutationCoeff(int n, int k)
{
    int Fn = 1, Fk;
  
    // Compute n! and (n-k)!
    for (int i = 1; i <= n; i++)
    {
        Fn *= i;
        if (i == n - k)
        Fk = Fn;
    }
    int coeff = Fn / Fk;
    return coeff;
}
  
// Driver Code
int main()
{
    int n = 10, k = 2;
    cout << "Value of P(" << n << ", " << k
         << ") is " << PermutationCoeff(n, k);
  
    return 0;
}

Java

// A O(n) time and O(1) extra 
// space solution to calculate
// the Permutation Coefficient
import java.io.*;
  
class GFG 
{
    static int PermutationCoeff(int n, 
                                int k)
    {
        int Fn = 1, Fk = 1;
      
        // Compute n! and (n-k)!
        for (int i = 1; i <= n; i++)
        {
            Fn *= i;
            if (i == n - k)
            Fk = Fn;
        }
        int coeff = Fn / Fk;
        return coeff;
    }
      
    // Driver Code 
    public static void main(String args[])
    {
        int n = 10, k = 2;
        System.out.println("Value of P( " + n + ","
                                         k +") is "
                            PermutationCoeff(n, k) );
    }
}
      
// This code is contributed by Nikita Tiwari.

Python3

# A O(n) time and O(1) extra 
# space solution to calculate
# the Permutation Coefficient
  
def PermutationCoeff(n, k):
    Fn = 1
  
    # Compute n! and (n-k)!
    for i in range(1, n + 1):
        Fn *= i
        if (i == n - k):
            Fk = Fn
  
    coeff = Fn // Fk
    return coeff
  
# Driver Code
n = 10
k = 2
print("Value of P(", n, ", ", k, ") is ",
       PermutationCoeff(n, k), sep = "")
  
# This code is contributed
# by Soumen Ghosh.

C#

// A O(n) time and O(1) extra 
// space solution to calculate
// the Permutation Coefficient
using System;
  
class GFG {
      
    static int PermutationCoeff(int n, 
                                int k)
    {
        int Fn = 1, Fk = 1;
      
        // Compute n! and (n-k)!
        for (int i = 1; i <= n; i++)
        {
            Fn *= i;
            if (i == n - k)
                Fk = Fn;
        }
        int coeff = Fn / Fk;
          
        return coeff;
    }
      
    // Driver Code 
    public static void Main()
    {
        int n = 10, k = 2;
        Console.WriteLine("Value of P( "
                   + n + "," + k +") is "
              + PermutationCoeff(n, k) );
    }
}
      
// This code is contributed by anuj_67.

PHP

<?php
// A O(n) time and O(1) extra 
// space PHP solution to calculate 
// the Permutation Coefficient
  
function PermutationCoeff( $n, $k)
{
    $Fn = 1; $Fk;
  
    // Compute n! and (n-k)!
    for ( $i = 1; $i <= $n; $i++)
    {
        $Fn *= $i;
        if ($i == $n - $k)
        $Fk = $Fn;
    }
    $coeff = $Fn / $Fk;
    return $coeff;
}
  
// Driver Code
$n = 10; $k = 2;
echo "Value of P(" , $n , ", " , $k , ")
        is " , PermutationCoeff($n, $k);
  
// This code is contributed by anuj_67. 
?>


Output :

Value of P(10, 2) is 90 

Thanks to Shiva Kumar for suggesting this solution.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter