Cuente el número de permutaciones de un Array que no tiene SubArray de tamaño dos o más del Array original

Dada una array de enteros distintos A , la tarea es contar el número de permutaciones posibles de la array dada A[] de modo que las permutaciones no contengan ningún subarreglo de tamaño 2 o más del arreglo original.
Ejemplos: 
 

Entrada: A = [1, 3, 9] 
Salida: 3 
Todas las permutaciones de [1, 3, 9] son: [1, 3, 9], [1, 9, 3], [3, 9, 1] , [ 3, 1, 9 ], [ 9, 1, 3 ], [ 9, 3, 1 ]
Aquí [ 1, 3, 9 ], [ 9, 1, 3 ] se eliminan porque contienen una subarray [ 1 , 3 ] de la lista original 
y [ 3, 9, 1 ] eliminado ya que contiene la subarray [3, 9] de la lista original, por lo que 
las siguientes son las 3 arrays que cumplen la condición: [1, 9, 3], [ 3, 1, 9], [9, 3, 1]
Entrada: A = [1, 3, 9, 12] 
Salida: 11 
 

Enfoque ingenuo: iterar a través de la lista de todas las permutaciones y eliminar las arrays que contienen cualquier sub-array [ i, i+1 ] de A .
A continuación se muestra la implementación del enfoque anterior: 
 

# Python implementation of the approach
 
# Importing the itertools
from itertools import permutations
 
# Function that return count of all the permutation
# having no sub-array of [ 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)):
 
            # Finding the indexes where x is present
            if z[j].index(x)!= len(z[j])-1:
 
                # If y is present at position of x + 1
                # append into a temp list q
                if z[j][z[j].index(x)+1]== y:
                    q.append(z[j])
 
    # Removing all the lists that are present
    # in z ( list of all permutations )
    for i in range(len(q)):
         if q[i] in z:
             z.remove(q[i])
    return len(z)
 
# Driver Code
A =[1, 3, 9]
print(count(A))

3

Solución eficiente: después de hacer la solución para el tamaño más pequeño de la array, podemos observar un patrón:
el siguiente patrón genera una recurrencia: 
suponga que la longitud de la array A es n, entonces: 
 

count(0) = 1
count(1) = 1
count(n) = n * count(n-1) + (n-1) * count(n-2)

A continuación se muestra la implementación del enfoque: 
 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Recursive function that returns
// the count of permutation-based
// on the length of the array.
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};
     
    // length of array
    int n = 4;
         
    // Output required answer
    cout << count(n - 1);
         
    return 0;
}
 
// This code is contributed by Sanjit Prasad

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Recursive function that returns
// the count of permutation-based
// on the length of the array.
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
public static void main(String[] args)
{
    int A[] = {1, 2, 3, 9};
     
    // length of array
    int n = 4;
         
    // Output required answer
    System.out.println(count(n - 1));
}
}
 
// This code is contributed by PrinciRaj1992

# Python implementation of the approach
 
# Recursive function that returns
# the count of permutation-based
# on the length of the 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 Code
A =[1, 2, 3, 9]
print(count(len(A)-1))

// C# implementation of the above approach
using System;
 
class GFG
{
 
// Recursive function that returns
// the count of permutation-based
// on the length of the array.
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
public static void Main(String[] args)
{
    int []A = {1, 2, 3, 9};
     
    // length of array
    int n = 4;
         
    // Output required answer
    Console.WriteLine(count(n - 1));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript implementation of the approach
 
// Recursive function that returns
// the count of permutation-based
// on the length of the 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 Code
 
let A = [1, 2, 3, 9];
 
// length of array
let n = 4;
 
// Output required answer
document.write(count(n - 1));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

11

Complejidad de tiempo: O(2^n)
Espacio auxiliar: O(1)