Given an array of integer A[] with no duplicate elements, write a function that returns the count of all the permutations of an array having no subarray of [i, i+1] for every i in A[].
Examples:
Input : 1 3 9
Output : 3
All the permutation of 1 3 9 are :
[1, 3, 9], [1, 9, 3], [3, 9, 1], [3, 1, 9], [9, 1, 3], [9, 3, 1]
Here [1, 3, 9], [9, 1, 3] are removed as they contain subarray
[1, 3] from original list and [3, 9, 1] removed as it contains
subarray [3, 9] from original list so,
Following are the 3 arrays that satisfy the condition :
[1, 9, 3], [3, 1, 9], [9, 3, 1]
Input : 1 3 9 12
Output : 11
Naive Solution: Generate all the permutations of an array and count all such permutations.
Efficient Solution : Following is a recursive solution based on fact that length of the array decides the number of all permutations having no subarray [i, i+1] for every i in A[ ]
Suppose the length of A[ ] is n, then
n = n-1
count(0) = 1
count(1) = 1
count(n) = n * count(n-1) + (n-1) * count(n-2)
Code : Below is the code for implementing the recursive function that return count of permutations
C++
// C++ implementation of the approach// Recursive function that return count of // permutation based on the length of array.#include <bits/stdc++.h>using namespace std;int count(int n){ if(n == 0) return 1; if(n == 1) return 1; else return (n * count(n - 1)) + ((n - 1) * count(n - 2));}// Driver codeint main(){ int A[] = {1, 2, 3, 9}; int len = sizeof(A) / sizeof(A[0]); cout << count(len - 1);}// This code is contributed by 29AjayKumar |
Java
// Java implementation of the approach// Recursive function that return count of // permutation based on the length of array.import java.util.*;class GFG{static int count(int n){ if(n == 0) return 1; if(n == 1) return 1; else return (n * count(n - 1)) + ((n - 1) * count(n - 2));}// Driver Codestatic public void main(String[] arg) { int []A = {1, 2, 3, 9}; System.out.print(count(A.length - 1));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python implementation of the approach# Recursive function that return count of # permutation based on the length of array.def count(n): if n == 0: return 1 if n == 1: return 1 else: return (n * count(n-1)) + ((n-1) * count(n-2)) # Driver CodeA = [1, 2, 3, 9]print(count(len(A)-1)) |
C#
// C# implementation of the approach// Recursive function that return count of // permutation based on the length of array.using System; class GFG{static int count(int n){ if(n == 0) return 1; if(n == 1) return 1; else return (n * count(n - 1)) + ((n - 1) * count(n - 2));}// Driver Codestatic public void Main(String[] arg) { int []A = {1, 2, 3, 9}; Console.Write(count(A.Length - 1));}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Recursive function that return count of // permutation based on the length of array.function count(n) { if(n == 0) return 1; if(n == 1) return 1; else return (n * count(n - 1)) + ((n - 1) * count(n - 2));}// Driver codelet A = [1, 2, 3, 9];let len = A.length;document.write(count(len - 1));// This code is contributed by Samim Hossain Mondal.</script> |
Output :
11
Time Complexity: O(n!), Finding pair for every element in the array of size n.
Auxiliary Space: O(n)
Brute Force Method :
Approach:
Our approach is very simple ,First we generate all the permutations of the given array and check if each permutation satisfies the given condition or not. We can do this by transversing through each element of the permutation and checking if it is adjacent to the next element in the original array or not.
Algorithms:
1.We can generate all the permutations of the given array A[].
2. For each permutation, we check if it contains any subarray of [i, i+1] for every i in A[].
If it does not contain any such subarray, we count it as a valid permutation.
To check if a permutation contains any subarray of [i, i+1], we can simply iterate through the permutation and check if any adjacent pair forms such subarray.
C++
#include <bits/stdc++.h>using namespace std;bool is_Valid_Permutation(vector<int>& permutation, vector<int>& arr) { for (int i = 0; i < permutation.size() - 1; i++) { int x = permutation[i], y = permutation[i + 1]; if (abs(x - y) == 1 && arr[x] < arr[y]) { return false; } } return true;}int count_Permutations(vector<int>& arr) { int n = arr.size(); vector<int> permutation(n); for (int i = 0; i < n; i++) { permutation[i] = i; } int count = 0; do { if (is_Valid_Permutation(permutation, arr)) { count++; } } while (next_permutation(permutation.begin(), permutation.end())); return count;}int main() { vector<int> arr = {1, 2, 3}; cout << count_Permutations(arr) << endl; arr = {1, 2, 3, 9}; cout << count_Permutations(arr) << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.Collections;public class PermutationCount { // Function to check if a given permutation is valid static boolean isValidPermutation(ArrayList<Integer> permutation, ArrayList<Integer> arr) { for (int i = 0; i < permutation.size() - 1; i++) { int x = permutation.get(i); int y = permutation.get(i + 1); // Check if the adjacent elements in the // permutation are consecutive and form an // increasing subsequence in the original array. if (Math.abs(x - y) == 1 && arr.get(x) < arr.get(y)) { return false; // If the condition is not // met, the permutation is not // valid. } } return true; // If all adjacent elements satisfy the // condition, the permutation is valid. } // Function to count valid permutations static int countPermutations(ArrayList<Integer> arr) { int n = arr.size(); ArrayList<Integer> permutation = new ArrayList<>(); for (int i = 0; i < n; i++) { permutation.add( i); // Create an initial permutation (0, 1, // 2, ..., n-1). } int count = 0; // Initialize the count of valid // permutations to 0. do { if (isValidPermutation(permutation, arr)) { count++; // If the current permutation is // valid, increment the count. } } while (nextPermutation( permutation)); // Generate all permutations // using lexicographic order. return count; // Return the total count of valid // permutations. } // Function to find the next permutation static boolean nextPermutation(ArrayList<Integer> permutation) { int i = permutation.size() - 2; // Find the longest suffix of the permutation that // is in non-increasing order. while (i >= 0 && permutation.get(i) >= permutation.get(i + 1)) { i--; } if (i < 0) { return false; // If the entire permutation is in // non-increasing order, there is // no next permutation. } int j = permutation.size() - 1; // Find the rightmost element in the suffix that is // greater than the current element // (permutation[i]). while (permutation.get(j) <= permutation.get(i)) { j--; } // Swap the current element with the next greater // element in the suffix. swap(permutation, i, j); // Reverse the suffix to get the next permutation in // lexicographic order. reverse(permutation, i + 1, permutation.size() - 1); return true; // Successfully generated the next // permutation. } // Function to swap two elements in an ArrayList static void swap(ArrayList<Integer> arr, int i, int j) { int temp = arr.get(i); arr.set(i, arr.get(j)); arr.set(j, temp); } // Function to reverse a portion of the ArrayList static void reverse(ArrayList<Integer> arr, int i, int j) { while (i < j) { swap(arr, i, j); i++; j--; } } public static void main(String[] args) { ArrayList<Integer> arr1 = new ArrayList<>(); arr1.add(1); arr1.add(2); arr1.add(3); System.out.println(countPermutations( arr1)); // Output: 2 (Valid permutations: (1, 3, // 2) and (2, 1, 3)) ArrayList<Integer> arr2 = new ArrayList<>(); arr2.add(1); arr2.add(2); arr2.add(3); arr2.add(9); System.out.println(countPermutations( arr2)); // Output: 0 (No valid permutation, as // (1, 3, 2, 9) breaks the increasing // subsequence condition) }} |
Output
3 11
Time Complexity: O(n*n!)
Auxiliary Space: O(n)
