If you want permutations with replacement, this exists and is called the cartesian product. Itertools has a function for this, product():
>>> for i in itertools.product('ABC', repeat=3): ... print i ... ('A', 'A', 'A') ('A', 'A', 'B') ('A', 'A', 'C') ('A', 'B', 'A') ('A', 'B', 'B') ('A', 'B', 'C') ('A', 'C', 'A') ('A', 'C', 'B') ('A', 'C', 'C') ('B', 'A', 'A') ('B', 'A', 'B') ('B', 'A', 'C') ('B', 'B', 'A') ('B', 'B', 'B') ('B', 'B', 'C') ('B', 'C', 'A') ('B', 'C', 'B') ('B', 'C', 'C') ('C', 'A', 'A') ('C', 'A', 'B') ('C', 'A', 'C') ('C', 'B', 'A') ('C', 'B', 'B') ('C', 'B', 'C') ('C', 'C', 'A') ('C', 'C', 'B') ('C', 'C', 'C')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:
Naive Solution :Iterate through list of all permutations and remove those arrays which contains any subarray [i, i+1] from A[ ].
Code: Python code for finding out the permutation
in the array
Python3
from itertools import permutations
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)
A = [1,3, 8, 9]
print(count(A))
Output :
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
Code : Below is the code for implementing the recursive function that return count of permutations
C++
#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));
}
int main()
{
int A[] = {1, 2, 3, 9};
int len = sizeof(A) / sizeof(A[0]);
cout << count(len - 1);
}
Java
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));
}
static public void main(String[] arg)
{
int []A = {1, 2, 3, 9};
System.out.print(count(A.length - 1));
}
}
Python3
def count(n):
if n == 0:
return 1
if n == 1:
return 1
else:
return (n * count(n-1)) + ((n-1) * count(n-2))
A = [1, 2, 3, 9]
print(count(len(A)-1))
C#
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));
}
static public void Main(String[] arg)
{
int []A = {1, 2, 3, 9};
Console.Write(count(A.Length - 1));
}
}
Javascript
<script>
function count(n) {
if(n == 0)
return 1;
if(n == 1)
return 1;
else
return (n * count(n - 1)) +
((n - 1) * count(n - 2));
}
let A = [1, 2, 3, 9];
let len = A.length;
document.write(count(len - 1));
</script>
Output :