educative.io

Why do you use a Deque in the non-recursive solution?

Courses
,
#1

In the task Permutations (medium), the non-recursive solution looks like this:

const Deque = require('./collections/deque'); //http://www.collectionsjs.com

function find_permutations(nums) {
  let numsLength = nums.length,
    result = [],
    permutations = new Deque();
  permutations.push([]);
  for (let i = 0; i < nums.length; i++) {
    const currentNumber = nums[i];
    // we will take all existing permutations and add the current number to create new permutations
    const n = permutations.length;
    for (let p = 0; p < n; p++) {
      const oldPermutation = permutations.shift();
      // create a new permutation by adding the current number at every position
      for (let j = 0; j < oldPermutation.length + 1; j++) {
        const newPermutation = oldPermutation.slice(0); // clone the permutation
        newPermutation.splice(j, 0, currentNumber); // insert currentNumber at index 'j'
        if (newPermutation.length === numsLength) {
          result.push(newPermutation);
        } else {
          permutations.push(newPermutation);
        }
      }
    }
  }

  return result;
}

Could you please explain why a Deque is necessary when a Queue or (for JS) a simple array would do the job just fine?

Thanks in advance

1 Like