 # Count all permutations of an array

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, The 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: iterate over the list of all permutations and remove those arrays that contain any subarray [i, i + 1] from A [] .

Code: Python code to define permutation in an array

` `

``` # Python implementation of the approach from i tertools import permutations    # A function that returns the number of all permutations # without subarray [i, i + 1]   def count (arr): z = [] perm = permutations (arr)   for i in list (perm):   z.append ( list (i)) q = []   for i in range ( len (arr) - 1 ):   x, y = arr [i], arr [i + 1 ]   for j in range ( len (z)): if z [j] .index (x)! = len (z [j]) - 1 : if z [j] [z [j] .index (x) + 1 ] = = y: q.append (z [ j])   for i in range ( len (q)): if q [i] in z: z.remove (q [i]) return len (z)   Driver code A = [ 1 , 3 , 8 , 9 ] print ( count (A)) ```

Output:

` 11 `

Efficient solution: Below is a recursive solution based on the fact that the length of an array determines the number of all permutations without a sublattice [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 to implement a recursive function that returns the number of permutations

C ++

` `

``` // C ++ implementation of the approach // Recurs An explicit function that returns the score // permutation based on the length of the array. # include & lt; bits / stdc ++. h & gt;  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 code int main () { int A [] = {1, 2, 3, 9};    int len = sizeof (A) / sizeof (A );  cout & lt; & lt; count (len - 1);  }   // This code is provided by 29AjayKumar ```

` ` Java

python3

 ` // Java implementation of the approach ` ` // Recursive function that returns the score ` ` // permutation based on array length. ` ` 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 code ` ` static ` ` public ` ` void ` ` main (String [] arg) ` ` {` ` int ` ` [] A = {` ` 1 ` `, ` ` 2 ` `, 3 , 9 }; ````   System.out.print (count (A.length - 1 ));  } }   // This code is provided by PrinciRaj1992 ```
 ` # Python implementation of the approach ` ` # Recursive function that returns count ` ` # permutation based on array length. `   ` 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 code ` ` A ` ` = ` ` [` ` 1 ` `, ` ` 2 ` `, ` ` 3 ` `, ` ` 9 ] ```` print (count ( len (A) - 1 )) ```

C #

` `

``` // C # implementation of the approach // Recursive function that returns the score // permutation based on array length. 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 code static public void Main (String [] arg)  { int [] A = {1, 2, 3 , nine};    Console.Write (count (A.Length - 1));  } }   // This code is provided by Princhi Singh ```

Output:

` 11 `