all blog posts


Recursively Concatenating Lists of Strings

In this blog post: how to recursively concatenate every element in an undefined number of lists.

For CloudBanshee we required every combination of an undefined number of lists. For example:

input = [
  ['a', 'b'],
  ['1', '2'],
  ['x', 'y']
];

output = [
  ['a1x', 'a1y', 'a2x', 'a2y', 'b1x', 'b1y', 'b2x', 'b2y']
]

Because we don't know the amount of lists in the input, we need a recursive function. Here it is (in Javascript):

function concatenateLists(inputLists, workingCopy = null) {
  // Break condition: return when inputLists is empty.
  if (inputLists.length === 0) {
    return workingCopy;
  }

  if (workingCopy === null) {
    // In the initial iteration, copy the first list
    // into the working copy.
    workingCopy = inputLists[0];
  } else {
    const tmp = [];
    // For every other iteration, take every item of
    // the working copy and append every item of the
    // first list in the inputLists.
    for (const wcItem of workingCopy) {
      for (const inputItem of inputLists[0]) {
        tmp.push(`${wcItem}${inputItem}`);
      }
    }
    // Overwrite the workingCopy with the new list.
    workingCopy = tmp;
  }
  // Recurse with the inputLists minus the first one.
  return concatenateLists(inputLists.slice(1), workingCopy);
}

const input = [
  ['a', 'b'],
  ['1', '2'],
  ['x', 'y']
];

const output = concatenateLists(input);
console.log(output); // (8) ["a1x", "a1y", "a2x", "a2y", "b1x", "b1y", "b2x", "b2y"]

For the first call, concatenateLists will be called as concatenateLists([ ['a', 'b'], ['1', '2'], ['x', 'y'] ]).

The second run will be concatenateLists([ ['1', '2'], ['x', 'y'] ], ['a', 'b']).

The third run will be concatenateLists([ ['x', 'y'] ], ['a1', 'a2', 'b1', 'b2']).

The fourth and final run will be concatenateLists([], ['a1x', 'a1y', 'a2x', 'a2y', 'b1x', 'b1y', 'b2x', 'b2y']).

This solution will work for any amount of input lists, with any amount of elements in each list. Of course it can also be used for other operations than concatenation.

If you have any questions, remarks, or suggestions to improve this solution, reach out to me on Twitter.


Related blog posts


all blog posts