Pairwise combinations of an array in Javascript

Question

I wrote a Javascript function that seems to successfully generate the unique pairwise combinations of a list:

function pairwise(list) {
  var pairs = [];
  list
    .slice(0, list.length - 1)
    .forEach(function (first, n) {
      var tail = list.slice(n + 1, list.length);
      tail.forEach(function (item) {
        pairs.push([first, item])
      });
    })
  return pairs;
}

pairwise('abcd'.split(''))
// [["a","b"],["a","c"],["a","d"],["b","c"],["b","d"],["c","d"]]

I checked it by using the combinatorics formula:

$$ combinations = \frac{n(n-1)}{2} $$

var alpha = [ "a", "b", "c", "d", "e", "f", "h", "i", "j" ];

for(var n=1;n<7;n++){ 
  console.log(
    n,                                 // number of items
    pairwise(alpha.slice(0,n)).length, // how many pairs from function?
    n*(n-1)/2                          // double check with formula above
  ); 
} 

// 1 0 0
// 2 1 1
// 3 3 3
// 4 6 6
// 5 10 10
// 6 15 15

Which looks right: there are 6 ways to chose pairs from 4 items, and so on.

It works, but I find it hard to read, and I'm not sure how to make it more readable. I'd welcome suggestions.

Answer 1

Your solution works fine, and it's fairly efficient. You're using loops and mutation, which are speedy, but also not terribly readable. This algorithm can be expressed more functionally in terms of recursion and mapping, which can make it somewhat more readable, though slightly less efficient.

function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = list[0],
      rest  = list.slice(1),
      pairs = rest.map(function (x) { return [first, x]; });
  return pairs.concat(pairwise(rest));
}

var result = pairwise(['a', 'b', 'c', 'd', 'e']);
console.log(result);
document.getElementById('output').innerHTML = JSON.stringify(result);

<pre id="output"></pre>

Additionally, if you're willing to use an external library, here's an equivalent solution using Lo-Dash. It's an identical algorithm, but it can help with readability to use a library designed for functional programming.

function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = _.first(list),
      rest  = _.rest(list),
      pairs = _.map(rest, function (x) { return [first, x]; });
  return _.flatten([pairs, pairwise(rest)], true);
}

var result = pairwise(['a', 'b', 'c', 'd', 'e']);
console.log(result);
document.getElementById('output').innerHTML = JSON.stringify(result);

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.4.1/lodash.min.js"></script>

<pre id="output"></pre>

Answer 2

Pairing combinations like this is a very common thing to do in any language. There's a very 'idiomatic' way to do this type of operation:

for (int i = 0; i < length; i++) {
    for (int j = i + 1; j < length; j++) {
        // do something with pair (i,j)
    }
}

You will see, and recognize this pattern anywhere.

Because that pattern is so recognizable, I prefer seeing it rather than the slicing and dicing your code does.

Additionally, since the formula for the number of iterations is so readily available, it makes sense to pre-size the output array you use. Pre-sizing the output array will make a significant performance difference.

Further, even though the 'classic' for loop is used here, the performance will be fine. Other systems requiring slices or maps of list subsets will require additional work which, despite being 'idiomatic', will not necessarily be faster:

function pairwise(list) {

    var pairs = new Array((list.length * (list.length - 1)) / 2),
        pos = 0;

    for (var i = 0; i < list.length; i++) {
        for (var j = i + 1; j < list.length; j++) {
            pairs[pos++] = [list[i], list[j]];
        }
    }
    return pairs;
}

var result = pairwise(['a', 'b', 'c', 'd', 'e']);
document.getElementById('output').innerHTML = JSON.stringify(result);  

<pre id="output"></pre>

Answer 3

Thanks for both of the very interesting and informative answers below, I learned a lot from your help.

I went with the recursive solution since I so heavily emphasized readability in the question. I find Alexis King’s answer remarkably clear:

function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = list[0],
      rest  = list.slice(1),
      pairs = rest.map(function (x) { return [first, x]; });
  return pairs.concat(pairwise(rest));
}

(Personally I find this much more readable than the lodash/underscore variant.)

That said, in production I would probably use rolfl’s solution, given the very convincing performance comparison. I do find myself trying to avoid for loops, not because I think they’re bad, but because I have a really hard time keeping the indices straight in my head.

One note on the issue of Array preallocation: I'm not sure that enhances speed. In the jsperf added by rolfl, the for-loop approach was fastest, but I added another test without the preallocation and it was still faster: http://jsperf.com/pairwise/2

Takehomes for me:

• for loops may not be as pretty as functional approaches but they're fast
• speed benefits from Array preallocation aren't necessarily clear
• recursion is beautiful but slow
• readability is relative to one's experience (I'm sure the for loop example is far more readable to more experienced programmers than it is to me)