13
\$\begingroup\$

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.

| improve this question | | | | |
\$\endgroup\$
  • \$\begingroup\$ This update should be in a self-answer instead. \$\endgroup\$ – Jamal Jan 5 '15 at 18:03
12
\$\begingroup\$

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>

| improve this answer | | | | |
\$\endgroup\$
15
\$\begingroup\$

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>

| improve this answer | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure that pre-sizing the array in JavaScript will really make a performance difference, since JS arrays are not actually arrays at all. \$\endgroup\$ – Alexis King Jan 4 '15 at 22:50
  • 4
    \$\begingroup\$ @AlexisKing - I put together a JSPerf for the performance: jsperf.com/push-or-preallocate - it's significantly faster to preallocate. \$\endgroup\$ – rolfl Jan 5 '15 at 1:10
  • 1
    \$\begingroup\$ @AlexisKing - FYI, I put all three pairwise processes in to jsperf here: jsperf.com/pairwise \$\endgroup\$ – rolfl Jan 5 '15 at 1:27
  • 1
    \$\begingroup\$ Fair enough, I stand corrected \$\endgroup\$ – Alexis King Jan 5 '15 at 1:29
2
\$\begingroup\$

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)
| improve this answer | | | | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.