Heap's algorithm to return array instead of printing

Question

I am trying to get this heaps algorithm to return an array of permutations instead of printing as below. I know it could be done by declaring an array outside of the function and pushing to it but, I want to avoid that approach. How can I make this return the array of permutations without using an outside array?

function heaps(arr, n) {
  if (n === undefined) n = arr.length;
  if (n <= 1) console.log(arr);
  else {
    for (let i = 0; i <= n - 1; i++)
     {
      heaps(arr, n-1);
      if 
        (n % 2 === 0) [arr[n-1], arr[i]] = [arr[i], arr[n-1]];
      else             
        [arr[n-1], arr[0]] = [arr[0], arr[n-1]];
    }
  }
}

Declare an array and an auxilliary function inside the outer function. — Pointy
– Pointy, Commented Oct 8, 2018 at 17:36

Bergi · Accepted Answer · 2018-10-08 20:27:06Z

2

Just make it return that result as an array, and collect return values from your recursive calls in the loop:

function heaps(arr, n = arr.length) {
  if (n <= 1) return [arr.slice()];
  let result = [];
  for (let i = 0; i <= n - 1; i++) {
    result.push(...heaps(arr, n-1));
    if (n % 2 === 0)
      [arr[n-1], arr[i]] = [arr[i], arr[n-1]];
    else             
      [arr[n-1], arr[0]] = [arr[0], arr[n-1]];
  }
  return result;
}

Alternatively, make an inner helper function that does push to an outer array

function heaps(arr) {
  let result = [];
  function helper(n) {
    if (n <= 1)
      result.push(arr.slice());
    else
      for (let i = 0; i <= n - 1; i++) {
        heaps(n-1);
        if (n % 2 === 0)
          [arr[n-1], arr[i]] = [arr[i], arr[n-1]];
        else             
          [arr[n-1], arr[0]] = [arr[0], arr[n-1]];
      }
  }
  helper(arr.length);
  return result;
}

If you insist on not using an "outer" array, make the result array and the input arr explicit parameters of the helper function.

answered Oct 8, 2018 at 20:27

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Roijjer Over a year ago

Thanks! The first one was what I was looking for. I was struggling with removing array layers that got returned from recursive calls.

Collectives™ on Stack Overflow

Heap's algorithm to return array instead of printing

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related