Javascript - Generating all combinations of elements in a single array (in pairs)

Question

I've seen several similar questions about how to generate all possible combinations of elements in an array. But I'm having a very hard time figuring out how to write an algorithm that will only output combination pairs. Any suggestions would be super appreciated!

Starting with the following array (with N elements):

var array = ["apple", "banana", "lemon", "mango"];

And getting the following result:

var result = [
   "apple banana"
   "apple lemon"
   "apple mango"
   "banana lemon"
   "banana mango"
   "lemon mango"
];

I was trying out the following approach but this results in all possible combinations, instead only combination pairs.

var letters = splSentences;
var combi = [];
var temp= "";
var letLen = Math.pow(2, letters.length);

for (var i = 0; i < letLen ; i++){
    temp= "";
    for (var j=0;j<letters.length;j++) {
        if ((i & Math.pow(2,j))){ 
            temp += letters[j]+ " "
        }
    }
    if (temp !== "") {
        combi.push(temp);
    }
}

Answer 1

A simple way would be to do a double for loop over the array where you skip the first i elements in the second loop.

let array = ["apple", "banana", "lemon", "mango"];
let results = [];

// Since you only want pairs, there's no reason
// to iterate over the last element directly
for (let i = 0; i < array.length - 1; i++) {
  // This is where you'll capture that last value
  for (let j = i + 1; j < array.length; j++) {
    results.push(`${array[i]} ${array[j]}`);
  }
}

console.log(results);

Rewritten with ES5:

var array = ["apple", "banana", "lemon", "mango"];
var results = [];

// Since you only want pairs, there's no reason
// to iterate over the last element directly
for (var i = 0; i < array.length - 1; i++) {
  // This is where you'll capture that last value
  for (var j = i + 1; j < array.length; j++) {
    results.push(array[i] + ' ' + array[j]);
  }
}

console.log(results);

Answer 2

Here are some functional programming solutions:

Using EcmaScript2019's flatMap:

var array = ["apple", "banana", "lemon", "mango"];

var result = array.flatMap(
    (v, i) => array.slice(i+1).map( w => v + ' ' + w )
);

console.log(result);

Before the introduction of flatMap (my answer in 2017), you would go for reduce or [].concat(...) in order to flatten the array:

var array = ["apple", "banana", "lemon", "mango"];

var result = array.reduce( (acc, v, i) =>
    acc.concat(array.slice(i+1).map( w => v + ' ' + w )),
[]);

console.log(result);

Or:

var array = ["apple", "banana", "lemon", "mango"];

var result = [].concat(...array.map( 
    (v, i) => array.slice(i+1).map( w => v + ' ' + w ))
);

console.log(result);

Answer 3

Although solutions have been found, I post here an algorithm for general case to find all combinations size n of m (m>n) elements. In your case, we have n=2 and m=4.

const result = [];
result.length = 2; //n=2

function combine(input, len, start) {
  if(len === 0) {
    console.log( result.join(" ") ); //process here the result
    return;
  }
  for (let i = start; i <= input.length - len; i++) {
    result[result.length - len] = input[i];
    combine(input, len-1, i+1 );
  }
}

const array = ["apple", "banana", "lemon", "mango"];    
combine( array, result.length, 0);

Answer 4

In my case, I wanted to get the combinations as follows, based on the size range of the array:

function getCombinations(valuesArray: String[])
{

var combi = [];
var temp = [];
var slent = Math.pow(2, valuesArray.length);

for (var i = 0; i < slent; i++)
{
    temp = [];
    for (var j = 0; j < valuesArray.length; j++)
    {
        if ((i & Math.pow(2, j)))
        {
            temp.push(valuesArray[j]);
        }
    }
    if (temp.length > 0)
    {
        combi.push(temp);
    }
}

combi.sort((a, b) => a.length - b.length);
console.log(combi.join("\n"));
return combi;
}

Example:

// variable "results" stores an array with arrays string type
let results = getCombinations(['apple', 'banana', 'lemon', ',mango']);

Output in console:

The function is based on the logic of the following documentation, more information in the following reference: https://www.w3resource.com/javascript-exercises/javascript-function-exercise-3.php

if ((i & Math.pow(2, j)))

Each bit of the first value is compared with the second, it is taken as valid if it matches, otherwise it returns zero and the condition is not met.

Answer 5

I ended up writing a general solution to this problem, which is functionally equivalent to nhnghia's answer, but I'm sharing it here as I think it's easier to read/follow and is also full of comments describing the algorithm.

/**
 * Generate all combinations of an array.
 * @param {Array} sourceArray - Array of input elements.
 * @param {number} comboLength - Desired length of combinations.
 * @return {Array} Array of combination arrays.
 */
function generateCombinations(sourceArray, comboLength) {
  const sourceLength = sourceArray.length;
  if (comboLength > sourceLength) return [];

  const combos = []; // Stores valid combinations as they are generated.

  // Accepts a partial combination, an index into sourceArray, 
  // and the number of elements required to be added to create a full-length combination.
  // Called recursively to build combinations, adding subsequent elements at each call depth.
  const makeNextCombos = (workingCombo, currentIndex, remainingCount) => {
    const oneAwayFromComboLength = remainingCount == 1;

    // For each element that remaines to be added to the working combination.
    for (let sourceIndex = currentIndex; sourceIndex < sourceLength; sourceIndex++) {
      // Get next (possibly partial) combination.
      const next = [ ...workingCombo, sourceArray[sourceIndex] ];

      if (oneAwayFromComboLength) {
        // Combo of right length found, save it.
        combos.push(next);
      }
      else {
        // Otherwise go deeper to add more elements to the current partial combination.
        makeNextCombos(next, sourceIndex + 1, remainingCount - 1);
      }
        }
  }

  makeNextCombos([], 0, comboLength);
  return combos;
}

Answer 6

Just to give an option for next who'll search it

const arr = ['a', 'b', 'c']
const combinations = ([head, ...tail]) => tail.length > 0 ? [...tail.map(tailValue => [head, tailValue]), ...combinations(tail)] : []
console.log(combinations(arr)) //[ [ 'a', 'b' ], [ 'a', 'c' ], [ 'b', 'c' ] ]

Answer 7

The best solutions I have found - https://lowrey.me/es6-javascript-combination-generator/ Uses ES6 generator functions, I adapted to TS. Most often you don't need all of the combinations at the same time. And I was getting annoyed by writing loops like for (let i=0; ... for let (j=i+1; ... for (let k=j+1... just to get combos one by one to test if I need to terminate the loops..

export function* combinations<T>(array: T[], length: number): IterableIterator<T[]> {
    for (let i = 0; i < array.length; i++) {
        if (length === 1) {
            yield [array[i]];
        } else {
            const remaining = combinations(array.slice(i + 1, array.length), length - 1);
            for (let next of remaining) {
                yield [array[i], ...next];
            }
        }
    }
}

usage:

for (const combo of combinations([1,2,3], 2)) {
    console.log(combo)
}

output:

> (2) [1, 2]
> (2) [1, 3]
> (2) [2, 3]

Answer 8

Using map and flatMap the following can be done (flatMap is only supported on chrome and firefox)

var array = ["apple", "banana", "lemon", "mango"]
array.flatMap(x => array.map(y => x !== y ? x + ' ' + y : null)).filter(x => x)

Answer 9

Generating combinations of elements in an array is a lot like counting in a numeral system, where the base is the number of elements in your array (if you account for the leading zeros that will be missing).

This gives you all the indices to your array (concatenated):

arr = ["apple", "banana", "lemon", "mango"]
base = arr.length

idx = [...Array(Math.pow(base, base)).keys()].map(x => x.toString(base))

You are only interested in pairs of two, so restrict the range accordingly:

range = (from, to) = [...Array(to).keys()].map(el => el + from)
indices = range => range.map(x => x.toString(base).padStart(2,"0"))

indices( range( 0, Math.pow(base, 2))) // range starts at 0, single digits are zero-padded.

Now what's left to do is map indices to values.

As you don't want elements paired with themselves and order doesn't matter, those need to be removed, before mapping to the final result.

const range = (from, to) => [...Array(to).keys()].map(el => el + from)
const combinations = arr => {
  const base = arr.length
  return range(0, Math.pow(base, 2))
    .map(x => x.toString(base).padStart(2, "0"))
    .filter(i => !i.match(/(\d)\1/) && i === i.split('').sort().join(''))
    .map(i => arr[i[0]] + " " + arr[i[1]])
}

console.log(combinations(["apple", "banana", "lemon", "mango"]))

With more than ten elements, toString() will return letters for indices; also, this will only work with up to 36 Elements.

Answer 10

I think it is an answer to all such questions.

/**
 * 
 * Generates all combination of given Array or number
 * 
 * @param {Array | number} item  - Item accepts array or number. If it is array exports all combination of items. If it is a number export all combination of the number
 * @param {number} n - pow of the item, if given value is `n` it will be export max `n` item combination
 * @param {boolean} filter - if it is true it will just export items which have got n items length. Otherwise export all posible length.
 * @return {Array} Array of combination arrays.
 * 
 * Usage Example:
 * 
 * console.log(combination(['A', 'B', 'C', 'D'], 2, true)); // [[ 'A','A' ], [ 'A', 'B' ]...] (16 items)
 * console.log(combination(['A', 'B', 'C', 'D'])); // [['A', 'A', 'A', 'B' ],.....,['A'],] (340 items)
 * console.log(comination(4, 2)); // all posible values [[ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 0, 0 ], [ 0, 1 ], [ 0, 2 ]...] (20 items)
 */
function combination(item, n) {
  const filter = typeof n !=='undefined';
  n = n ? n : item.length;
  const result = [];
  const isArray = item.constructor.name === 'Array';
  const count = isArray ? item.length : item;

  const pow = (x, n, m = []) => {
    if (n > 0) {
      for (var i = 0; i < count; i++) {
        const value = pow(x, n - 1, [...m, isArray ? item[i] : i]);
        result.push(value);
      }
    }
    return m;
  }
  pow(isArray ? item.length : item, n);

  return filter ? result.filter(item => item.length == n) : result;
}

console.log("#####first sample: ", combination(['A', 'B', 'C', 'D'], 2)); // with filter
console.log("#####second sample: ", combination(['A', 'B', 'C', 'D'])); // without filter
console.log("#####third sample: ", combination(4, 2)); // gives array with index number

Answer 11

Here is an non-mutating ES6 approach combining things (TS):

function combine (tail: any[], length: number, head: any[][] = [[]]): any[][] {
  return tail.reduce((acc, tailElement) => {
    const tailHeadVariants = head.reduce((acc, headElement: any[]) => {
      const combination = [...headElement, tailElement]
      return [...acc, combination]
    }, [])
    if (length === 1) return [...acc, tailHeadVariants]
    const subCombinations = combine(tail.filter(t => t !== tailElement), length - 1, tailHeadVariants)
    return [...acc, ...subCombinations]
  }, [])
}

Answer 12

Generating combinations is a classic problem. Here's my interpretation of that solution:

const combinations = (elements) => {
    if (elements.length == 1) {
        return [elements];
    } else {
        const tail = combinations(elements.slice(1));
        return tail.reduce(
            (combos, combo) => { combos.push([elements[0], ...combo]); return combos; },
            [[elements[0]], ...tail]
        );
    }
};

const array = ["apple", "banana", "lemon", "mango"];
console.log(combinations(array));

Answer 13

Beating a dead horse a bit, but with smaller sets where recursion limit and performance is not a problem, the general combination generation can be done recursively with "recurse combinations containing the first element in given array" plus "recurse combinations not containing the first element". It gives quite compact implementation as a generator:

// Generator yielding k-item combinations of array a
function* choose(a, k) {
  if(a.length == k) yield a;
  else if(k == 0) yield [];
  else {
      for(let rest of choose(a.slice(1), k-1)) yield [a[0], ...rest];
      for(let rest of choose(a.slice(1), k)) yield rest;
  }
}

And even slightly shorter (and twice faster, 1 M calls of 7 choose 5 took 3.9 seconds with my MacBook) with function returning and array of combinations:

// Return an array of combinations
function comb(a, k) {
  if(a.length === k) return [a];
  else if(k === 0) return [[]];
  else return [...comb(a.slice(1), k-1).map(c => [a[0], ...c]),
      ...comb(a.slice(1), k)];
}