Pairwise combinations of entries in a javascript array

Question

I'm given an array of entries in javascript, such as :

var entries = ["cat", "dog", "chicken", "pig"];

I'd now like to iterate over all unique pairwise combinations of them. In this example, I'd like to see:

("cat", "dog"),
("cat", "chicken"),
...

In other languages, like scala, this is super easy. You just do

entries.combinations(2)

is there a similar method or function in a library for javascript? Or do I just have to write it myself the ugly way with nested loops?

Anopheles

Yes, you have to write it yourself. – Airframe

Answer 1

Not as far as I know. I think you have to stick to nested loops.

A similar question has been asked here: Output each combination of an array of numbers with javascript maybe you can find an answer there.

Claireclairobscure

Ah, too bad. And yes, that is the same as my question! It seems i failed to find it when searching. – Anopheles

I wish Lodash had this – Morie

Answer 2

var arr = ["cat","dog","chicken","pig"].map(function(item,i,arr) {
    return arr.map(function(_item) { if( item != _item) return [item, _item];});
});

This will return the expected results. There are caveats, it does not work in older browsers without shims.

Also the duplicate value is 'undefined' instead of there being 4 arrays of 3. I'm sure there is a more graceful way to handle this.

Array.prototype.map() - MDN

edit

this will give you the proper pairwise combinations.

var arr = ["cat","dog","chicken","pig"].map(function(item,i,arr) {
    var tmp = arr.map(function(_item) { if( item != _item) return [item, _item];});
    return tmp.splice(tmp.indexOf(undefined),1), tmp;
});

Array splice method - MDN

and here is a more readable version of the same code.

var myArray = ["cat", "dog", "chicken", "pig"];
var pairwise = myArray.map(function(item, index, originalArray) {
    var tmp = originalArray.map(function(_item) {
        if (item != _item) {
            return [item, _item];
        }
    });
    tmp.splice(tmp.indexOf(undefined), 1); // because there is now one undefined index we must remove it.
    return tmp;
});

Jumpoff

Here it is in the prototype jsfiddle.net/rlemon/qtxHx if you find you need to use it often. – Jumpoff

Answer 3

With ES6 syntax, one can use a shorter version of @rlemon's answer:

["cat","dog","chicken","pig"].sort().reduce(
  (acc, item, i, arr) => acc.concat(
    arr.slice(i + 1).map(_item => [item, _item])
  ),
[])

This takes care of undefineds, and also outputs only unique combinations, as per OP's question.

Borgeson

Answer 4

After reviewing the question, this answer doesn't correctly solve the question. The question asks for all combinations, but the function below combines all adjacent even and odd indexes of the array.

Here is a pairwise implementation I did using reduce

function pairwise(arr) {
    return arr.reduce(function(acc, current, index) {
        var isFirstPair = (index % 2) === 0;

        if (isFirstPair) {
            acc.push([current]);
        } else {
            lastElement = acc[acc.length - 1];
            lastElement.push(current);
        }

        return acc;
    }, []);
};

var nums = [1,2,3,4,5,6];

var res = pairwise(nums);

res.forEach(function(elem) {
   console.log(elem); 
});

Returns:

[
  [1, 2]
  [3, 4]
  [5, 6]
]

Habilitate

I think reduce and forEach won't work on IE8 developer.mozilla.org/en-US/docs/JavaScript/Reference/… – Fantast

The forEach isn't really relevant as it's only use for demo purposes here. Although the reduce is problematic on IE8 as you say. I'm sure you could shim it though. – Habilitate

I see my solution isn't really answering the question. He's asking for all combinations, but I'm providing a solution that gives a combination of all even and odd elements of the array. – Habilitate

Answer 5

Here's a generic TypeScript implementation (you can get the pure JS by removing the types):

// Returns an array of size
const sizedArray = (n: number): null[] => Array(n).fill(null);

// calls the callback n times
const times = (n: number, cb: () => void): void => {
  while (0 < n--) {
    cb();
  }
};

// Fills up the array with the return values of subsequent calls of cb
const fillWithCb = <T>(n: number, cb: () => T): T[] => sizedArray(n).map(cb);

// Generic to produce pairwise, 3 element wise etc..
const nWise = (n: number): (<T>(array: T[]) => T[][]) => <T>(
  array: T[]
): T[][] => {
  const iterators = fillWithCb(n, () => array[Symbol.iterator]());
  iterators.forEach((it, index) => times(index, () => it.next()));
  return fillWithCb(array.length - n + 1, () =>
    iterators.map(it => it.next().value)
  );
};

// curried nWise with 2 -> pairWise
export const pairWise = nWise(2);

Embattled

Answer 6

The most effective and simple solution can be reduced and slice. However, if you just want to get values. You can use a generator.

// Util class 
function pairWise(arr) {
     return {
         [Symbol.iterator]: function *() {
             for(let i =0; i< arr.length; i= i+2)
             yield arr.slice(i, i+2)
         }
     }
    } 
 // How to use it
for(ent of pairWise([1,2,3,4,5,6, 7])){
    console.log(ent)
}
// Output
/*
[ 1, 2 ]
[ 3, 4 ]
[ 5, 6 ]
[ 7 ]
*/

Weismann