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.
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.
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.
// A O(n) solution that uses
// table fact[] to calculate
// the Permutation Coefficient
#include<bits/stdc++.h>
using namespace std;
// Returns value of Permutation
// Coefficient P(n, k)
int permutationCoeff( int n, int k)
{
`` int fact[n + 1];
`` // Base case
`` fact[0] = 1;
`` // Calculate 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;
``
`` cout << "Value of P(" << n << ", "
`` << k << ") is "
`` << permutationCoeff(n, k);
`` return 0;
}
Output :
Value of P(10, 2) is 90
A O(n) time and O(1) Extra Space Solution
// 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 P = 1;
`` // Compute n*(n-1)*(n-2)....(n-k+1)
`` for ( int i = 0; i < k; i++)
`` P *= (n-i) ;
`` return P;
}
// Driver Code
int main()
{
`` int n = 10, k = 2;
`` cout << "Value of P(" << n << ", " << k
`` << ") is " << PermutationCoeff(n, k);
`` return 0;
}
Output :
Value of P(10, 2) is 90