Javascript Algorithm:Restricted Permutations (Certain elements always occurs together )

Permutation:

A permutation is an arrangement of objects in definite order. For example, the

number of permutation of set A={1,6} is 2, i.e. {1,6}, {6,1}. As you can see,

there are no other ways to arrange the elements of set A.

In permutation, the elements should be arranged in a particular order whereas in

combination the order of elements does not matter.

Restricted permutations:

Restricted permutations are permutations where certain elements are always

either included or excluded. In addition to this, it also refers to the

permutations that can either always occur together or always stay apart.

Types of restrictions that may be applied:

1) Certain elements that are always included

2) Certain elements that are permanently excluded

3) Certain elements that consistently occur together

4) Certain elements that always stay apart

Problem Statement:

For given elements 1,2,3,..n without any repetation how many distinct

permutation can be made such that first element is 1 while remaining n-1 element

can be any of 2,3,...n-1 in any order.

Solution :

function permute(nums) {

let result = [];

if (nums.length == 1) {

return [nums];

}

for (let i = 0; i < nums.length; i++) {

let firstElement = nums[i]; //first element

//remaining element array

let remaining = nums.filter((elem) => {

return elem != firstElement;

});

let perms = permute(remaining);

for (let perm of perms) {

perm.push(firstElement);

}

result.push(...perms);

}

return result;

}

function getRestrictedPermutaion(nums) {

let result = [];

let firstElement = nums[0];//1 is at 0th position here

let remaining = nums.filter((elem) => {

return elem != firstElement;

});

let intermediateResult = permute(remaining);

result.push(...intermediateResult);

result = result.map((elem)=>{

elem.unshift(1)

return elem

})

return result;

}

let result = getRestrictedPermutaion([1, 2, 3]);

console.log(result);

Lets modify this problem to be more generic.

New Problem Statement:

For given elements 1,2,3,...,n and 1<= t <= n find all permutations such that

1,2,3...t will remain as first t elements while other t,t+1,...n can be in any

order.

Solution:

function permute(nums) {

let result = [];

if (nums.length <= 1) {

return [nums];

}

for (let i = 0; i < nums.length; i++) {

let firstElement = nums[i]; //first element

//remaining element array

let remaining = nums.filter((elem) => {

return elem != firstElement;

});

let perms = permute(remaining);

for (let perm of perms) {

perm.push(firstElement);

}

result.push(...perms);

}

return result;

}

function getRestrictedPermutaion(firstElementArray, nums) {

let result = [];

let remaining = nums.filter((elem) => {

return !firstElementArray.includes(elem);

});

let intermediateResult = permute(remaining);

result.push(...intermediateResult);

result = result.map((elem) => {

let newElement = firstElementArray.concat(elem);

return newElement;

});

return result;

}

let result = getRestrictedPermutaion([1, 2, 3], [1, 2, 3, 4, 5, 6]);

console.log(result);

Note: Here type of restriction is certain elements consistently

occur together