Given two positive integers n and k, the task is to count the number of special permutations. A special permutation P is defined as a permutation of first n natural numbers in which there exists at least (n – k) indices such that Pi = i.
Prerequisite: Derangements
Examples:
Input: n = 4, k = 2
Output: 7
{1, 2, 3, 4}, {1, 2, 4, 3}, {4, 2, 3, 1}, {2, 1, 3, 4}, {1, 4, 3, 2}, {1, 3, 2, 4} and {3, 2, 1, 4} are the only possible special permutations.Input: n = 5, k = 3
Output: 31
Approach: Let the function fx denote the number of special permutations in which there exists exactly x indices such that Pi = i. Hence, the required answer will be:
f(n – k) + f(n – k + 1) + f(n – k + 2) + … + f(n – 1) + fn
Now, fx can be calculated by choosing x indices from n where Pi = i and calculating the number of derangements for (n – i) other indices as for them Pi should not be equal to i then multiplying the result by nCx as there can be different ways to select x indices from n.
Steps to solve the problem:
- Define a function nCr to calculate the number of combinations of n items taken r at a time using the formula n! / (r! * (n-r)!)
- Define a function countDerangements to calculate the number of derangements of n items using the formula der(n) = (n-1) * (der(n-1) + der(n-2)) where der(0) = 1 and der(1) = 0.
- Define a function countPermutations to calculate the number of permutations of n items where no more than k items are in their original positions using the following steps.
- Initialize a variable ans to 0.
- Loop through i from n-k to n.
- Calculate the number of ways to choose i items from n items using the nCr function.
- Calculate the number of derangements of n-i items using the countDerangements function.
- Multiply the number of ways and the number of derangements and add the result to and.
- Return ans as the result of the function.
Below is the implementation of the above approach:
C++
// C++ program to count the number// of required permutations#include <bits/stdc++.h>using namespace std;#define ll long long int// Function to return the number of ways// to choose r objects out of n objectsint nCr(int n, int r){ int ans = 1; if (r > n - r) r = n - r; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans;}// Function to return the number// of derangements of nint countDerangements(int n){ int der[n + 1]; der[0] = 1; der[1] = 0; der[2] = 1; for (int i = 3; i <= n; i++) der[i] = (i - 1) * (der[i - 1] + der[i - 2]); return der[n];}// Function to return the required// number of permutationsll countPermutations(int n, int k){ ll ans = 0; for (int i = n - k; i <= n; i++) { // Ways to choose i indices from n indices int ways = nCr(n, i); // Derangements of (n - i) indices ans += ways * countDerangements(n - i); } return ans;}// Driver Code to test above functionsint main(){ int n = 5, k = 3; cout << countPermutations(n, k); return 0;} |
Java
// Java program to count the number // of required permutations public class GFG{ // Function to return the number of ways // to choose r objects out of n objects static int nCr(int n, int r) { int ans = 1; if (r > n - r) r = n - r; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; } // Function to return the number // of derangements of n static int countDerangements(int n) { int der[] = new int[ n + 3]; der[0] = 1; der[1] = 0; der[2] = 1; for (int i = 3; i <= n; i++) der[i] = (i - 1) * (der[i - 1] + der[i - 2]); return der[n]; } // Function to return the required // number of permutations static int countPermutations(int n, int k) { int ans = 0; for (int i = n - k; i <= n; i++) { // Ways to choose i indices from n indices int ways = nCr(n, i); // Derangements of (n - i) indices //System.out.println(ans) ; ans += (ways * countDerangements(n- i)); } return ans; } // Driver Code to test above functions public static void main(String []args) { int n = 5, k = 3; System.out.println(countPermutations(n, k)) ; } // This code is contributed by Ryuga} |
Python3
# Python 3 program to count the number# of required permutation# function to return the number of ways # to chooser objects out of n objectsdef nCr(n, r): ans = 1 if r > n - r: r = n - r for i in range(r): ans *= (n - i) ans /= (i + 1) return ans# function to return the number of# degrangemnets of ndef countDerangements(n): der = [0 for i in range(n + 3)] der[0] = 1 der[1] = 0 der[2] = 1 for i in range(3, n + 1): der[i] = (i - 1) * (der[i - 1] + der[i - 2]) return der[n]# function to return the required # number of permutationsdef countPermutations(n, k): ans = 0 for i in range(n - k, n + 1): # ways to choose i indices # from n indices ways = nCr(n, i) # Derangements of (n-i) indices ans += ways * countDerangements(n - i) return ans# Driver Coden, k = 5, 3print(countPermutations(n, k))# This code is contributed by# Mohit kumar 29 (IIIT gwalior) |
C#
// C# program to count the number // of required permutationsusing System; public class GFG{ // Function to return the number of ways // to choose r objects out of n objects static int nCr(int n, int r) { int ans = 1; if (r > n - r) r = n - r; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; } // Function to return the number // of derangements of n static int countDerangements(int n) { int []der = new int[ n + 3]; der[0] = 1; der[1] = 0; der[2] = 1; for (int i = 3; i <= n; i++) der[i] = (i - 1) * (der[i - 1] + der[i - 2]); return der[n]; } // Function to return the required // number of permutations static int countPermutations(int n, int k) { int ans = 0; for (int i = n - k; i <= n; i++) { // Ways to choose i indices from n indices int ways = nCr(n, i); // Derangements of (n - i) indices //System.out.println(ans) ; ans += (ways * countDerangements(n- i)); } return ans; } // Driver Code to test above functions public static void Main() { int n = 5, k = 3; Console.WriteLine(countPermutations(n, k)) ; } }// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to count the number // of required permutations // Function to return the number of ways // to choose r objects out of n objects function nCr(n, r) { var ans = 1; if (r > n - r) r = n - r; for (var i = 0; i < r; i++) { ans *= n - i; ans /= i + 1; } return ans; } // Function to return the number // of derangements of n function countDerangements(n) { var der = [...Array(n + 1)]; der[0] = 1; der[1] = 0; der[2] = 1; for (var i = 3; i <= n; i++) der[i] = (i - 1) * (der[i - 1] + der[i - 2]); return der[n]; } // Function to return the required // number of permutations function countPermutations(n, k) { var ans = 0; for (var i = n - k; i <= n; i++) { // Ways to choose i indices from n indices var ways = nCr(n, i); // Derangements of (n - i) indices ans += ways * countDerangements(n - i); } return ans; } // Driver Code to test above functions var n = 5, k = 3; document.write(countPermutations(n, k)); </script> |
PHP
<?php// PHP program to count the number// of required permutations// Function to return the number of ways// to choose r objects out of n objectsfunction nCr($n, $r){ $ans = 1; if ($r > $n - $r) $r = $n - $r; for ($i = 0; $i < $r; $i++) { $ans *= ($n - $i); $ans /= ($i + 1); } return $ans;}// Function to return the number// of derangements of nfunction countDerangements($n){ $der = array($n + 1); $der[0] = 1; $der[1] = 0; $der[2] = 1; for ($i = 3; $i <= $n; $i++) $der[$i] = ($i - 1) * ($der[$i - 1] + $der[$i - 2]); return $der[$n];}// Function to return the required// number of permutationsfunction countPermutations($n, $k){ $ans = 0; for ($i = $n - $k; $i <= $n; $i++) { // Ways to choose i indices // from n indices $ways = nCr($n, $i); // Derangements of (n - i) indices $ans += $ways * countDerangements($n - $i); } return $ans;}// Driver Code$n = 5;$k = 3;echo (countPermutations($n, $k));// This code is contributed // by Shivi_Aggarwal ?> |
Output
31
Time Complexity: O(N^2), since there runs a loop inside another loop.
Auxiliary Space: O(N), since N extra space has been taken.
Efficient approach : Space optimization O(1)
In previous approach we the current value dp[i] is only depend upon the previous 2 values i.e. dp[i-1] and dp[i-2]. So to optimize the space we can keep track of previous and current values by the help of three variables prev1, prev2 and curr which will reduce the space complexity from O(N) to O(1).
Implementation Steps:
- Create 2 variables prev1 and prev2 to keep track o previous values of DP.
- Initialize base case prev1 = 0 and prev2 = 1.
- Create a variable curr to store current value.
- Iterate over subproblem using loop and update curr.
- After every iteration update prev1 and prev2 for further iterations.
- At last return curr.
Implementation:
C++
// C++ program to count the number// of required permutations#include <bits/stdc++.h>using namespace std;#define ll long long int// Function to return the number of ways// to choose r objects out of n objectsint nCr(int n, int r){ int ans = 1; if (r > n - r) r = n - r; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans;}// Function to return the number// of derangements of nint countDerangements(int n){ // to store previous values of DP int prev0=1 , prev1=0 , prev2=1; // to store current value int curr; // Base Case if(n == 0) return prev0; if(n == 1) return prev1; if(n == 2) return prev2; // iterate over subproblems to gee the current // value from previous computations for (int i = 3; i <= n; i++){ curr = (i-1) * ( prev2 + prev1 ) ; // assigning values for further iterations prev1 = prev2; prev2 = curr; } // return answer return curr;}// Function to return the required// number of permutationsll countPermutations(int n, int k){ ll ans = 0; for (int i = n - k; i <= n; i++) { // Ways to choose i indices from n indices int ways = nCr(n, i); // Derangements of (n - i) indices ans += ways * countDerangements(n - i); } return ans;}// Driver Code to test above functionsint main(){ int n = 5, k = 3; cout << countPermutations(n, k); return 0;} |
Java
import java.util.*;public class Main { // Function to return the number of ways // to choose r objects out of n objects public static int nCr(int n, int r) { int ans = 1; if (r > n - r) r = n - r; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; } // Function to return the number // of derangements of n public static int countDerangements(int n) { // to store previous values of DP int prev0=1 , prev1=0 , prev2=1; // to store current value int curr; // Base Case if(n == 0) return prev0; if(n == 1) return prev1; if(n == 2) return prev2; // iterate over subproblems to gee the current // value from previous computations for (int i = 3; i <= n; i++){ curr = (i-1) * ( prev2 + prev1 ) ; // assigning values for further iterations prev1 = prev2; prev2 = curr; } // return answer return prev2; } // Function to return the required // number of permutations public static long countPermutations(int n, int k) { long ans = 0; for (int i = n - k; i <= n; i++) { // Ways to choose i indices from n indices int ways = nCr(n, i); // Derangements of (n - i) indices ans += ways * countDerangements(n - i); } return ans; } // Driver Code to test above functions public static void main(String[] args) { int n = 5, k = 3; System.out.println(countPermutations(n, k)); }} |
Python
# Python program to count the number# of required permutationsimport math# Function to return the number of ways# to choose r objects out of n objectsdef nCr(n, r): ans = 1 if (r > n - r): r = n - r for i in range(r): ans *= (n - i) ans //= (i + 1) return ans# Function to return the number# of derangements of ndef countDerangements(n): # to store previous values of DP prev0, prev1, prev2 = 1, 0, 1 # Base Case if n == 0: return prev0 if n == 1: return prev1 if n == 2: return prev2 # iterate over subproblems to get the current # value from previous computations for i in range(3, n + 1): curr = (i - 1) * (prev2 + prev1) # assigning values for further iterations prev1 = prev2 prev2 = curr # return answer return curr# Function to return the required# number of permutationsdef countPermutations(n, k): ans = 0 for i in range(n - k, n + 1): # Ways to choose i indices from n indices ways = nCr(n, i) # Derangements of (n - i) indices ans += ways * countDerangements(n - i) return ans# Driver Code to test above functionsif __name__ == '__main__': n = 5 k = 3 print(countPermutations(n, k)) |
C#
using System;public class Program{ // Function to return the number of ways // to choose r objects out of n objects static int nCr(int n, int r) { int ans = 1; if (r > n - r) r = n - r; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; } // Function to return the number // of derangements of n static int CountDerangements(int n) { // to store previous values of DP int prev0 = 1, prev1 = 0, prev2 = 1; // to store current value int curr = 0; // Initialize curr // Base Case if (n == 0) return prev0; if (n == 1) return prev1; if (n == 2) return prev2; // iterate over subproblems to get the current // value from previous computations for (int i = 3; i <= n; i++) { curr = (i - 1) * (prev2 + prev1); // assigning values for further iterations prev1 = prev2; prev2 = curr; } // return answer return curr; } // Function to return the required // number of permutations static long CountPermutations(int n, int k) { long ans = 0; for (int i = n - k; i <= n; i++) { // Ways to choose i indices from n indices int ways = nCr(n, i); // Derangements of (n - i) indices ans += ways * CountDerangements(n - i); } return ans; } // Driver Code public static void Main() { int n = 5, k = 3; Console.WriteLine(CountPermutations(n, k)); }} |
Javascript
// Function to return the number of ways// to choose r objects out of n objectsfunction nCr(n, r) { let ans = 1; if (r > n - r) r = n - r; for (let i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans;}// Function to return the number// of derangements of nfunction countDerangements(n) { // to store previous values of DP let prev0 = 1, prev1 = 0, prev2 = 1; // to store current value let curr; // Base Case if (n === 0) return prev0; if (n === 1) return prev1; if (n === 2) return prev2; // iterate over subproblems to get the current // value from previous computations for (let i = 3; i <= n; i++) { curr = (i - 1) * (prev2 + prev1); // assigning values for further iterations prev1 = prev2; prev2 = curr; } // return answer return curr;}// Function to return the required// number of permutationsfunction countPermutations(n, k) { let ans = 0; for (let i = n - k; i <= n; i++) { // Ways to choose i indices from n indices let ways = nCr(n, i); // Derangements of (n - i) indices ans += ways * countDerangements(n - i); } return ans;}// Driver Code to test above functionslet n = 5, k = 3;console.log(countPermutations(n, k)); |
Output
31
Time Complexity: O(N^2), since there runs a loop inside another loop.
Auxiliary Space: O(1), since no extra space is used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
