Heap Algorithm

by Vadim Costin

JavaScript

//jshint esversion: 6

//implementation from
//https://en.wikipedia.org/wiki/Heap%27s_algorithm

function permAlone(str) {
  const solutions = generateHeapSolutions(str);
  const filterSolutions = solutions.filter(isCharactersNotRepeatConsecutive);
  return filterSolutions.length;
}

function isCharactersNotRepeatConsecutive(str){
  return !/(.)\1+/g.test(str);
}

function swap(arr, index1, index2){
	let tmp = arr[index1];
  let arrForMutate = arr;
  arrForMutate[index1] = arrForMutate[index2];
  arrForMutate[index2] = tmp;
  return arrForMutate;
}

function generateHeapSolutions(str = 'AB'){
		let A = str.split('');
    let c = [];
    let solutions = [];
    let n = A.length;

    for(let i = 0; i < n; i++){
    	c[i] = 0;
    }            
    solutions.push(A.join(''));
    
    let i = 0;
    while (i < n){    
      if(c[i] < i){
        if (i % 2 === 0){
          A = swap(A, 0, i);
        } else {
          A = swap(A, c[i], i);
        }
        solutions.push(A.join(''));
        c[i] ++;
        i = 0;
      } else {
        c[i] = 0;
        i ++;
      }
    } 
    return solutions;
 }
 
console.log(permAlone('aab'));