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]);
}

Lucite

Welcome to StackOverflow! What would you expect to happen if there were repeated digits? Would there be repeated combinations in the answers, or should each appear only once? – Broomcorn

BTW, you should search the site for relevant answers. Do any of these results help you? – Broomcorn

@ScottSauyet Good point. It should be repeated in the output array. Thank you for pointing that out, I have updated the question to reflect that! I will check out those answers tomorrow, thanks Scott – Lucite

If you’re looking for a non-“concatenated” variant of permutations, i.e. from an array [ "5", "7", "9" ] generating [ [ "5", "7", "9" ], [ "7", "5", "9" ], [ "9", "5", "7" ],…], see Permutations in JavaScript?. – Involuted

Answer 1

Heap's algorithm can be used to generate all permutations (without repetitions) of array elements, you can then use those permutations with array.join("") to convert them to strings. This works for arrays of any size and any type:

Here is a quick javascript implementation:

// some global variable to store the results
var result = []

// currentSize should be invoked with the array size
function permutation(arr, currentSize) {
    if (currentSize == 1) { // recursion base-case (end)
        result.push(arr.join(""));
        return;
    }
    
    for (let i = 0; i < currentSize; i++){
        permutation(arr, currentSize - 1);
        if (currentSize % 2 == 1) {
            let temp = arr[0];
            arr[0] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        } else {
            let temp = arr[i];
            arr[i] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        }
    }
}

let array = ["1","2","3","4"];
permutation(array, array.length);

console.log(result);
// use result here

Keep in mind that this is very computationally expensive, with complexity of O(n!).

Igneous

Thank you very much Viktor! This worked perfectly. For any other learners I would recommend this video which helped me understand the algorithm link – Lucite

Answer 2

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.

Acetylcholine

Very nice. I love the colored circle illustrations, but especially also the breakdown using * map and * chain. Very useful. – Broomcorn

Answer 3

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']

Broomcorn

you might have seen it here :D I like your name rotations and agree it's useful as its own function. I will decompose mine and adopt your name, if you don't mind – Acetylcholine

@Thank you. Of course I don't mind. That's what SO is for: to learn, borrow, and steal from one another. If there is any accounting, I'm much deeper in your debt than the reverse. Yes, yours was the same algorithm, but I was actually thinking of this answer, which I must have looked at during some recent permutations search. So you're actually adopting Chris Vouga's term. – Broomcorn

haha no accounting on this end. i get what i come here for and you play a big role in that, so continued and perpetual thanks Scott. i'm now working on an iterative permutations that can yield the results lazily, and it's more challenging than i thought. i'll keep you updated with an progress i make :D – Acetylcholine

@Thankyou: If you simply want to use a generator function, my first approach can be easily modified: function * permutations (xs) {if (xs.length == 0) yield []; for (let i = 0; i < xs. length; i ++) for (let p of permutations (excluding (i) (xs))) yield [xs[i], ...p]} Of course this uses an ugly indexed for in the outer loop, but I don't have an immediate alternative. – Broomcorn

thanks for the shove to get actually complete this. it took a bit to isolate the moving parts that make permutations tick, but i'm pretty happy with the result. i'll have to run some benchmarks tomorrow to see how dreadful the performance is compared to Heap's... – Acetylcholine

Answer 4

The following might serve your need after adjusting argument to accept array instead of a number.

function combinator(nbr) {
  if (typeof nbr !== 'number' || nbr>999999999) return 'NaN'
 const combinedArr = []
 const _nbr = `${nbr}`.split('')
 combinatorRec(_nbr, [])

 function combinatorRec(_nbr, prev){
   if (_nbr.length === 0) {
     combinedArr.push(parseInt(prev))
     return
   }
  _nbr.forEach((char,i)=>{
    const _nbrI = [..._nbr]
    _nbrI.splice(i,1)
    combinatorRec(_nbrI, prev+char )
  })
 }

  const uniqueArray = combinedArr.filter((item, pos) => (combinedArr.indexOf(item) === pos))
 return uniqueArray
}

Quetzalcoatl

Welcome to StackOverflow! Can I suggest that you edit this question to actually make the nbr -> array alteration? That way the answer actually matches the question. Also, I'd suggest two changes. Replace the two lines that create _nbrI and then modify it with one: const _nbrI = [..._nbr.slice(0, i), ..._nbr.slice(i + 1)] And replace the definition of uniqueArray with const uniqueArray = [...new Set (combinedArr)], which is more idiomatic modern JS and is likely faster. – Broomcorn