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 [0]); 

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