javascript - 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

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!).