Heap's Algorithm

Heap's Algorithm
0.0 0

#1
var swap = function (array, pos1, pos2) {
  var temp = array[pos1];
  array[pos1] = array[pos2];
  array[pos2] = temp;
};

var heapsPermute = function (array, output, n) {
  n = n || array.length; // set n default to array.length
  if (n === 1) {
    output(array);
  } else {
    for (var i = 1; i <= n; i += 1) {
      heapsPermute(array, output, n - 1);
      if (n % 2) {
        var j = 1;
      } else {
        var j = i;
      }
      swap(array, j - 1, n - 1); // -1 to account for javascript zero-indexing
    }
  }
};


// For testing:
var print = function(input){
  console.log(input);
}

heapsPermute(['a', 'b', 'c', 'd'], print);

Hello there. I have a question about this algorithm. It lists every permutation of an array.

[ 'a', 'b', 'c', 'd' ]
[ 'b', 'a', 'c', 'd' ]
[ 'c', 'a', 'b', 'd' ]
[ 'a', 'c', 'b', 'd' ]
[ 'b', 'c', 'a', 'd' ]
etc...

I was wondering if anyone could tell me a way to modify this algorithm so that it gives every permutation of length n from an array of letters.
For example if n is 2:

['a', 'b']
['a', 'c']
['a', 'd']
etc...

Thank you for taking the time to read my question. Any help much appreciated.


#2

This is the technical definition of a heap’s algo according to this repo of algos https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations

A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself

Therefore I don’t think what you ask can be solved with this algorithm, since it needs to have a one-to-one correspondence (same size). Unless what you are looking for is to just splice a portion of the results so that

[ 'a', 'b', 'c', 'd' ]
[ 'b', 'a', 'c', 'd' ]
[ 'c', 'a', 'b', 'd' ]
[ 'a', 'c', 'b', 'd' ]
[ 'b', 'c', 'a', 'd' ]
etc...

// becomes
[ 'a', 'b' ]
[ 'c', 'd' ]
[ 'b', 'a' ]
[ 'c', 'd' ]
[ 'c', 'a' ]
[ 'b', 'd' ]
[ 'a', 'c' ]
[ 'b', 'd' ]
[ 'b', 'c' ]
[ 'a', 'd' ]
etc...

#3

OK, just curious. Is there any reason that your solution must use Heap’s or do you just need a solution that gives that result?

You could probably come up with some way to pare down the array to length = n many times and feed those pared down arrays to your Heap’s function but there are easier ways to calculate those results.


#4

[ ‘a’, ‘b’, ‘c’, ‘d’ ]
[ ‘b’, ‘a’, ‘c’, ‘d’ ]
[ ‘c’, ‘a’, ‘b’, ‘d’ ]
[ ‘a’, ‘c’, ‘b’, ‘d’ ]
[ ‘b’, ‘c’, ‘a’, ‘d’ ]
etc…

// becomes
[ ‘a’, ‘b’ ]
[ ‘c’, ‘d’ ]
[ ‘b’, ‘a’ ]
[ ‘c’, ‘d’ ]
[ ‘c’, ‘a’ ]
[ ‘b’, ‘d’ ]
[ ‘a’, ‘c’ ]
[ ‘b’, ‘d’ ]
[ ‘b’, ‘c’ ]
[ ‘a’, ‘d’ ]
etc…


#5

OK - not sure if this is faithful to Heap’s algorithm but I believe it does what you are asking.

// calculate permutations of elements in an array
// params 
// arr - arr of items to permutate
// [len] - optional length of permutation if less than arr.length
// [repeat] optional allow repeat use of array items defaults to false

function permutations(arr, len, repeat = false) {
	
  len = len || arr.length;
  if(len > arr.length) len = arr.length;
  const results = [];

	function eliminate(el, arr) {
		let i = arr.indexOf(el);
		arr.splice(i, 1);
		return arr;
	}

	function perms(arr, len, prefix = []) {
		if (prefix.length === len) {
			results.push(prefix);
		} else {
			for (let elem of arr) {
				let newPrefix = [...prefix];
				newPrefix.push(elem);
    
        let newRest = null;

        if(repeat){
          newRest = arr;
        }else{
          newRest = eliminate(elem, [...arr]);
        }
				
	 perms(newRest, len, newPrefix);
	}
 }
		return;
	}
	perms(arr, len);

	return results;
}

// using all places, no repeats as expected with Heap's
console.log(permutations(['a', 'b', 'c', 'd', 'e']).length);

// limited to 3 places, no repeat use of elements
console.log(permutations(['a', 'b', 'c', 'd', 'e'],3).length);

// limited to 3 places, allowing repeat use of elements
console.log(permutations(['a', 'b', 'c', 'd', 'e'],3, true).length);

#6

Hi there alhazen1. I apologize for my untimely response. Thank you for your solution. It seems to work very well. I shall study it further later on today. It being faithful to Heap’s or not is not important. I should have clarified that in my original post. Thank you again for your help.