CODEWITHSUNDEEP
javascriptarraysdata-structurespermutation
NAVIN
NAVIN

Reputation: 3317

How to make permutaion pair without using global variable in JavaScript?

I need to create an array of all the possible combination of an array elements, like permutation a vary wide spread data structure question. To follow more about question can check here at random hacks, geeksforgeeks and math world.

Note: Don't want to use any JS library, just data structure here

Question is simple, an array is provided and needs to find all possible combinations like:

arr = [1,2,3];
combination = [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]];
// combination.length is factorial of arr.length

To achieve this I had created a global variable to store combinations, need to do this without global variable, I'm unable to do so, can anyone help me figure out this, here's my code:

let ans = [];  // Global variable to store combinations

function permute(arr) {
  let l = arguments[1] || 0,
      r = arguments[2] || arr.length-1;

  if (l == r) {
    let a = [];

    a.push(...arr);  // To overcome reference problem here.
    ans.push(a);
  }
  else {
    for (let i = l; i <= r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
      permute(arr, l+1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
    }
  }

  return ans;
}

console.log(permute([1,2,3,4]));
console.log(permute([1,2,3]));
console.log(permute([1,2,3,4,5]));

Thank You for trying out and helping.

Upvotes: 0

Views: 129

Answers (5)

Nitish Narang
Nitish Narang

Reputation: 4184

You can also try using Array.map with recursion like below to achieve permutation. I have also used Array.flat (as of now not supported by Edge, and needs polyfill if Edge browser is to support)

function getForwardArr(arr, i) {
  return [...arr.slice(i+1), ...arr.slice(0, i)]
}

function permute(arr) {
  if (arr.length == 2) return [[...arr], arr.reverse()]
  else return arr.map((d, i) => permute(getForwardArr(arr, i)).map(v => [d, v].flat())).flat()
}

console.log(permute([1,2]))

console.log(permute([1,2,3]))

console.log(permute([1,2,3,4]))

Upvotes: 1

slider
slider

Reputation: 12990

Another way to do this is not to pass "down" anything but to reuse results of smaller subproblems to build your permutations array and return that.

So, for example, to build all 3 element permutations, you would put each element in the first place and concatenate it with all 2 element permutations of the remaining elements (which you would obtain with a recursive call):

function permutations(arr) {
  if (arr.length <= 1) return [arr];
  var res = [];
  arr.forEach((e, i) => {
    var smaller = permutations([...arr.slice(0, i), ...arr.slice(i + 1)]);
    smaller.forEach(p => res.push([e].concat(p)))
  });
  return res;
}

console.log(permutations([1]));
console.log(permutations([1, 2, 3]));

Upvotes: 0

Jonas Wilms
Jonas Wilms

Reputation: 138267

I'd use an additional parameter to pass down the current chosen elements to the function and a generator to pass all the results back up:

 function* permutations(array, positions = [], previous = []) {
  if(previous.length === array.length) yield previous;

  for(let i = 0; i < array.length; i++) {
   if(positions.includes(i)) continue;

   const chosen = array[i];
   yield* permutations(array, [...positions, i], [...previous, chosen]);
  }
}

const permutate = arr => [...permutations(arr)];

Upvotes: 2

fedeghe
fedeghe

Reputation: 1318

If the only concern is the global var you can simply wrap it in another function, I mean something like the following:

function permute(_arr) {
  let ans = [];
  (function _permute(arr) {
    let l = arguments[1] || 0,
      r = arguments[2] || arr.length - 1;

    if (l == r) {
      let a = [];

      a.push(...arr);  // To overcome reference problem here.
      ans.push(a);
    }
    else {
      for (let i = l; i <= r; i++) {
        [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
        _permute(arr, l + 1, r);
        [arr[l], arr[i]] = [arr[i], arr[l]];  // Swap with help of new destructuring
      }
    }
  })(_arr);
  return ans;
}

console.log(permute([1, 2, 3, 4]));
console.log(permute([1, 2, 3]));
console.log(permute([1, 2, 3, 4, 5]));

Upvotes: 1

Jacek Lipiec
Jacek Lipiec

Reputation: 432

You are doing recursion without passing an accumulator. To alleviate this, do...

function permuteRecursive(permutees, accumulator) {
  // if not created before, create first instance of accumulator
  accumulator = accumulator || [];

  let l = arguments[2] || 0,
      r = arguments[3] || permutees.length-1;

  if (l == r) {
    let a = [];

    a.push(...permutees);  // To overcome reference problem here.
    accumulator.push(a);
  }
  else {
    for (let i = l; i <= r; i++) {
      [permutees[l], permutees[i]] = [permutees[i], permutees[l]];  // Swap with help of new destructuring
      permuteRecursive(permutees, accumulator, l+1, r);
      [permutees[l], permutees[i]] = [permutees[i], permutees[l]];  // Swap with help of new destructuring
    }
  }

  return accumulator;
}

console.log(permuteRecursive([1,2,3,4]));
console.log(permuteRecursive([1,2,3]));
console.log(permuteRecursive([1,2,3,4,5]));

Upvotes: 2

Related Questions