Recurse through single array logging all possible permutations in javascript

Question

For example, I have an array

["red", "green", "blue", "purple"]

There can be any amount of entries in this array. Using this array I want to create a list of possible permutations but never duplicating an item in the array (no repetition)

For example, the above array will result in

red,green,blue,purple
red,green,purple,blue
red,blue,green,purple
red,blue,purple,green
red,purple,blue,green
red,purple,green,blue

green,red,blue,purple
green,red,purple,blue
green,blue,red,purple
green,blue,purple,red
green,purple,blue,red
green,purple,red,blue

blue,red,green,purple
blue,red,purple,green
blue,green,red,purple
blue,green,purple,red
blue,purple,green,red
blue,purple,red,green

purple,red,green,blue
purple,red,purple,blue
purple,green,red,blue
purple,green,blue,red
purple,blue,green,red
purple,blue,red,green

I am new to recursion and I havent quite gripped how to accomplish this with it,

EDIT The answer originally mentioned "combinations", but the technical term for what the OP is looking for is "permutation"; see the OP's comment below, and learn more about combination vs permutation vs variation, here (at least one difference: in permutations, order matters, in combinations, order does not)

Answered here http://stackoverflow.com/questions/9960908/permutations-in-javascript — Grzegorz Kaczan, Mar 27 '13 at 20:44
Thanks, I didn't know it was called permutation. Thanks for the link — Wesley Skeen, Mar 27 '13 at 20:46

score 0 · Accepted Answer · edited Jul 11 '23 at 01:06

0

function combs(arr,str){
  var arrCopy,popped;
  for(var i =0; i<arr.length; i++){
     arrCopy = arr.splice(0);
     popped = arrCopy.splice(i,1)
     combs(arrCopy,popped);
  }
  if(arr.length === 0){
    console.log(str);
  }
}

That will log all the options to the console. If you need to return them all in some format you can return instead of printing at the base case, and concat the results of the recursive calls together as necessary.

function allcombs(a) {
  var all = [];

  function combs(arr, str) {
    var arrCopy, popped;
    for (var i = 0; i < arr.length; i++) {
      arrCopy = arr.splice(0);
      popped = arrCopy.splice(i, 1)
      combs(arrCopy, popped);
    }
    if (arr.length === 0) {
      all.push(str);
      console.log(str);
    }
  }
  combs(a);
  return all;
}

edited Jul 11 '23 at 01:06

Nate Anderson

18,334
18
100
135

answered Mar 27 '13 at 20:42

Ben McCormick

25,260
12
52
71

Thanks, This would of done it. I got an answer from this link stackoverflow.com/questions/9960908/permutations-in-javascript, just before you added this – Wesley Skeen Mar 27 '13 at 20:49
2

Just tried this today. All it does is print one item of the array, not the combination. – Raymond Camden Dec 09 '15 at 11:15
I downvoted because I agree with @RaymondCamden, please "@" me if you edit the answer and I will I remove my downvote. – Nate Anderson Jul 11 '23 at 01:31

score 0 · Answer 2 · answered Mar 27 '13 at 20:44

0

You could start with this:

http://rosettacode.org/wiki/Permutations#JavaScript

It's implemented to output to an HTML element, but you should be able to easily adapt it to meet your needs.

answered Mar 27 '13 at 20:44

Mike Van Til

133
1
7

This is a [link-only answer](https://meta.stackexchange.com/a/8259/313336), can you please edit, maybe include the relevant snippet from rosettacode? – Nate Anderson Jul 11 '23 at 00:55

score 0 · Answer 3 · answered Jul 11 '23 at 01:29

The accepted answer only logs arrays of length 1. If you give it an array with 4 distinct items, you expect all the permutations (it should log 4! = 4*3*2*1 = 24 items, but it only logs 3 items (and a fourth undefined?))

Here I adapted the accepted answer to something that logs all expected permutations. I left comments on the specific lines of the accepted answer that I changed. I'll remove my downvote once the accepted answer is edited. You see how my answer is consistent with this other SO answer on permutations. You can see a JSFiddle here

function allcombs(a) {
  var all = [];
    var permuteCount = 0;

  function combs(arr, str) {
    permuteCount++;
    var arrCopy, popped, str = str || []; // initialize str 
    console.error(arr.length);
    for (var i = 0; i < arr.length; i++) {
      arrCopy = arr.slice(0); // need to slice (copies values out of arr), not splice (moves values out and *empties* arr; affecting the *if* check at the end of this function
      popped = arrCopy.splice(i, 1)
      combs(arrCopy, str.concat(popped)); // <- need to concatenate to accumulate results
    }
    if (arr.length === 0) {
      all.push(str);
      console.log(str);
    }
  }
  combs(a);
    console.error(permuteCount);
  return all;
}

var result = JSON.stringify(allcombs(["red", "green", "blue", "purple"]), null, 4).replace(/],/g, '],<br/>');

// document.body.innerHTML = result;
console.log('final result ', result);

Recurse through single array logging all possible permutations in javascript

3 Answers3

Linked