Finding all permutations of array elements as concatenated strings

Question

I am trying to write a JavaScript function that returns all combinations of the elements of an array of unknown length. The argument to be passed to the function should be an array of single digit strings e.g. [ "5", "7", "9" ].

An example to illustrate the desired functionality:

• If you pass in an array of [ "5", "7", "9" ], it should return an array with all the possible 3-digit combinations of those 3 numbers i.e. [ "579", "759", "957", "795",…].
• If you passed in an array of [ "2", "5", "4", "6" ], you would get the 4-digit combinations of those 4 numbers, i.e. [ "2546", "2654", "2465",…].
• If you passed in an array of length 5, you would get the 5-digit combinations of those 5 numbers, and so on.
• If the inputted array has the same digit multiple times, that number should appear multiple times in the resulting array e.g. an input of [ "5", "5", "6" ] produces an output of [ "556", "655", "565",…].

I have looked around and it seems that recursion might be the way to go, but I am struggling to get it working. I have attempted the below solution which currently works for 3-digit numbers but I can’t figure out how to make a function which works with an array of unknown length.

function getDoubleDigitCombinations(input) {
  let result = [];
  const first = input[0];
  const last = input[1];

  result.push(first + last);
  result.push(last + first);

  return result;
}


function getTripleDigitCombinations(input) {
  let result = [];
  let main; // This is the number in question.
  let other1; // These are the other numbers.
  let other2;

  for (i = 0; i < input.length; i++) {
    let arr = input.slice(); // Make a copy of the input array.
    
    main = input[i];
    arr.splice(i, 1); // Remove the main element from the array …
    other1 = arr[0]; // … so that you are left with the other two numbers.
    other2 = arr[1];

    console.log(`Main is ${main}`);
    console.log(`other1 is ${other1} and other2 is ${other2}`);

    const arr2 = getDoubleDigitCombinations([other1, other2]); // Get the combinations of the others.

    result.push(main + arr2[0]); // Concatenate main with both of the others combinations.
    result.push(main + arr2[1]);
  }

  return result;
}

let result2 = getTripleDigitCombinations([ "6", "7", "8" ]);

console.log("result2 is ...");

for (i = 0; i < result2.length; i++) {
  console.log(result2[i]);
}

Answer 1

A fun problem! I wanted to implement using generators. This allows you to work with the permutations one-by-one as they are generated, rather than having to compute all permutations before the entire answer is provided -

const input =
  ["🔴","🟢","🔵","🟡"]

for (const p of permutations(input))
  console.log(p.join(""))

🔴🟢🔵🟡
🟢🔴🔵🟡
🟢🔵🔴🟡
🟢🔵🟡🔴
🔴🔵🟢🟡
🔵🔴🟢🟡
🔵🟢🔴🟡
🔵🟢🟡🔴
🔴🔵🟡🟢
🔵🔴🟡🟢
🔵🟡🔴🟢
🔵🟡🟢🔴
🔴🟢🟡🔵
🟢🔴🟡🔵
🟢🟡🔴🔵
🟢🟡🔵🔴
🔴🟡🟢🔵
🟡🔴🟢🔵
🟡🟢🔴🔵
🟡🟢🔵🔴
🔴🟡🔵🟢
🟡🔴🔵🟢
🟡🔵🔴🟢
🟡🔵🟢🔴

This allows us to do cool things like, finding specific patterns -

// find all permutations where red is left of green
for (const p of permutations(input))
  if (p.indexOf("🔴") < p.indexOf("🟢"))
    console.log(p.join(""))

🟡🔵🔴🟢
🔵🟡🔴🟢
🔵🔴🟢🟡
🔵🔴🟡🟢
🟡🔴🟢🔵
🟡🔴🔵🟢
🔴🟢🟡🔵
🔴🟡🟢🔵
🔴🟡🔵🟢
🔴🟢🔵🟡
🔴🔵🟢🟡
🔴🔵🟡🟢

// find all permutations where blue and yellow are adjacent
for (const p of permutations(input))
  if (Math.abs(p.indexOf("🔵") - p.indexOf("🟡")) == 1)
    console.log(p.join(""))

🟢🟡🔵🔴
🟡🔵🟢🔴
🟡🔵🔴🟢
🟢🔵🟡🔴
🔵🟡🟢🔴
🔵🟡🔴🟢
🟢🔴🟡🔵
🔴🟢🟡🔵
🔴🟡🔵🟢
🟢🔴🔵🟡
🔴🟢🔵🟡
🔴🔵🟡🟢

And if we wanted to find the only the first permutation where such a condition is true, we can use return or break to stop the generator and no more permutations will be computed.

---

We just have to implement permutations -

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

Which depends on rotations -

function* rotations (t, v)
{ if (t.length == 0)
    yield [v]
  else
    yield *chain
      ( [[v, ...t]]
      , map(rotations(t.slice(1), v), r => [t[0], ...r])
      )
}

Which depends on two generic functions for working with iterables, map and chain -

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

Expand the snippet to verify the results in your own browser

function* permutations (t)
{ if (t.length < 2)
    yield t
  else
    for (const p of permutations(t.slice(1)))
      for (const r of rotations(p, t[0]))
        yield r
}

function* rotations (t, v)
{ if (t.length == 0)
    yield [v]
  else
    yield *chain
      ( [[v, ...t]]
      , map(rotations(t.slice(1), v), r => [t[0], ...r])
      )
}

function* map (t, f)
{ for (const e of t)
    yield f(e)
}

function* chain (...ts)
{ for (const t of ts)
    for (const e of t)
      yield e
}

const input =
  ["🔴","🟢","🔵","🟡"]

console.log("\nred is left of green")
for (const p of permutations(input))
  if (p.indexOf("🔴") < p.indexOf("🟢"))
    console.log(p.join(""))

console.log("\nblue and yellow are adjacent")
for (const p of permutations(input))
  if (Math.abs(p.indexOf("🔵") - p.indexOf("🟡")) == 1)
    console.log(p.join(""))

I hope you enjoyed this post as much as I enjoyed writing it :D

To compute combinations using a similar technique, see this related Q&A.

Answer 2

Heap's algorithm is still, I believe, the gold standard for efficiency. Victor's answer covers that well.

But since any algorithm has to be at least O(n!), we're never going to get stunning performance in generating permutations. We might want to look also at simplicity.

Another implementation is decidedly simpler:

const excluding = (i) => (xs) => 
  [... xs .slice (0, i), ... xs .slice (i + 1)]

const permutations = (xs) => 
  xs .length == 0 
    ? [[]] 
    : xs .flatMap ((x, i) => permutations (excluding (i) (xs)) .map (p => x + p))

console .log (permutations (['5', '6', '7']))

Here we use a small helper function, excluding, which returns a copy of an array removing the value at a given index. Then permutations loops over the values in the array, taking each in turn to be the first value of a set of permutations, and finding the remainder of those permutations by recurring on the array found by excluding the current index.

This has the nice feature that the permutations are returned in an obvious order. If the original array is sorted, say ['a', 'b', 'c'], then the results are returned in alphabetic order: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. This is not usually essential, but it can be useful.

Note that this solution is more commonly written with this line:

    : xs .flatMap ((x, i) => permutations (excluding (i) (xs)) .map (p => [x, ... p]))

which returns an array of arrays ([['5', '6', '7'], ['5', '7', '6'], ...]) instead of an array of strings (['567', '576', ...]).

---

There is another version which I've seen recently that is even simpler. It's not original, but I don't recall where I saw it -- probably here on StackOverflow. This is my own implementation of that idea, but I think it's pretty close to the original:

const rotations = ([l, ...ls], rs = []) => 
  l == undefined ? [] : [[l, ...ls, ...rs], ... rotations (ls, [...rs, l])]

const permutations = ([l, ...ls]) =>
  l == undefined ? [[]] : [...permutations (ls) .flatMap (p => rotations ([l, ...p])) ]

console .log (permutations (['5', '6', '7']) .map (p => p .join ('')))

.as-console-wrapper {max-height: 100% !important; top: 0}

Here we use a function rotations which takes an array and returns all the wrapped-around rotations of that array. For example:

rotations(['x', 'y', 'z'])
//=> [['x', 'y', 'z'], ['y', 'z', 'x'], ['z', 'x', 'y']]

We use that to write permutations by taking out the first element, recursively finding the permutations of the remaining elements, and for each, sticking the first element back on and returning all the rotations.

This is short and quite clever. I would probably stick to either Heap's algorithm for speed or to the one above for the nicely ordered output. But this one is still worth considering for the simplicity.

While this algorithm could be fixed up to return strings, it would be more intrusive than it was in the previous version, involving changes to both rotations and permutations, and I would prefer to stick to generating the strings on the output of it as done above with .map (p => p .join ('')). If you wanted to do it, though, it might look like this:

const rotations = ([l, ...ls], rs = '') => 
  l == undefined ? [] : [l + ls.join('') + rs, ... rotations (ls, rs + l)]

const permutations = ([l, ...ls]) =>
  l == undefined ? [[]] : [...permutations (ls) .flatMap (p => rotations (l + p)) ]

permutations (['5', '7', '7']) //=> ['577', '775', '757', '577', '775', '757']