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);
    }
}

Hungarian

Here is one that takes any number of string, not just two #66109281 – Initiative

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);

Nipa

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);

Drupelet

Add some spread operator for more beauty instead of concat(). :D – Scharaga

Your second answer is better written using flatMap() in order to not have nested arrays of subsets: result = [...array.flatMap((v1,i) => array.slice(i+1).map(v2 => v1+' '+v1))] – Canonical

Thanks for your comment, @Phrogz. I updated my answer. When I wrote this answer in 2017, flatMap was not yet widely available. NB: here there is no need to spread the result of flatMap. – Drupelet

Answer 3

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.

Electron

Please consider adding some comments on how your code achieves the result so it would be easier for others to understand – Ironsides

Thank you! for your suggestion – Electron

Can You please explain to me what this part of code is doing ? if ((i & Math.pow(2, j))) { temp.push(valuesArray[j]); } – Percutaneous

Hey, can you explain, please, what this code does? if ((i & Math.pow(2, j))) – Linet

If you like one-liners, you can try this Codepen: const combinations = (arr) => [...Array(2 ** arr.length - 1).keys()].map((n) => ((n + 1) >>> 0).toString(2).split("").reverse().map((n, i) => (+n ? arr[i] : false)).filter(Boolean)).sort((a, b) => (a.length > b.length ? 1 : -1)); console.log(combinations(["apple", "banana", "lemon", "mango"])); – Equitable

Great script, thanks! – Blaylock

Please remove the extra comma from mango - I tried to do it, but SO doesn't allow edits less than 6 chars! :-( ['apple', 'banana', 'lemon', ',mango'] <<< 'mango' – Beardsley

I optimized this script with bitwise operators and some es6. Feel free to use it Codepen – Harrod

Answer 4

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);

Commonly

can you mention the time complexity of this algorithm ? – Redhanded

That result.length = 2 is so harsh to the eyes. Also a shame that the function is not "self contained" (pure function...). – Rie

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;
}

Kubetz

Working algorithm extensively explained and with very explicit naming convention. – Rie

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' ] ]

Amor

Functional programming inspired. – Rie

And a version that creates all combinations of all 3? abc acb bca bac - etc? – Initiative

@Initiative That's not called combinations. That's called permutations. They're different. cuemath.com/algebra/… – Leduc

@Leduc Sure, but I needed permutations at the time and I liked this script – Initiative

@Initiative you may want to look at the answer for permutations instead – Leduc

@Leduc I got a solution the same day I believe. Thanks though – Initiative

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]

Arman

only problem i can say it generates combinations in one way only, i was looking for combinations([1,2,3], 2) to give [1,2][2,1][1,3][3,1][2,3][3,2] – Luciferin

no probs just did it var combinations=function*(e,i){for(let l=0;l<e.length;l++)if(1===i)yield[e[l]];else{let n=combinations(e.slice(l+1,e.length),i-1);for(let i of n)yield[e[l],...i],yield[...i,e[l]]}}; – Luciferin

Those are permutations, not combinations – Arman

Wish is right: what @Luciferin is looking for is permutations (which consider element order) not combinations (which are unordered groupings). See cuemath.com/algebra/… – Amur

Answer 8

There is also this answer: https://mcmap.net/q/262860/-can-you-return-n-choose-k-combinations-in-javascript-using-array-flatmap

The alghorithm is this answer generates all the possible sets of combination(or choose(n, k)) of n items within k spaces.

The algorhitm:

function choose(arr, k, prefix=[]) {
    if (k == 0) return [prefix];
    return arr.flatMap((v, i) =>
        choose(arr.slice(i+1), k-1, [...prefix, v])
    );
}

console.log(choose([0,1,2,3,4], 3));

I had a similar problem and this algorhitm is working very well for me.

Teplitz

Elegance plus the k param makes this the winner for me! – Bothy

Answer 9

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)

Mcmillen

How to change this same code for a combination of 4 digits and filter only the 4 digit number which gives sum 9 ? var array = [0,1, 2, 3, 4,5,6,7,8,9] array.flatMap(x => array.map(y => x !== y ? x + ' ' + y : null)).filter(x => x) asw eg, 7227,7776.... – Birthright

Answer 10

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.

Prentice

I think the idea is cool and worth taking note, although the algorithm might be a bit too complex for such a problem. – Rie

Answer 11

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

Plunk

Nice but this is also giving the combinations with repeated elements like 'AA' which is not what the OP asked for. – Rie

Yes, it gives. I guess, a simple if statement will be the solution. – Plunk

This actually gives the permutations with repetition – Brownie

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));

Anthracosis

Answer 13

As this post is well indexed on Google under the keywords "generate all combinations", lots of people coming here simply need to generate all the unique combinations, regardless of the size of the output (not only pairs).

This post answers this need.

All unique combinations, without recursion:

    const getCombos = async (a) => {
      const separator = '';
      const o = Object();
      for (let i = 0; i < a.length; ++i) {
        for (let j = i + 1; j <= a.length; ++j) {
          const left = a.slice(i, j);
          const right = a.slice(j, a.length);
          o[left.join(separator)] = 1;
          for (let k = 0; k < right.length; ++k) {
            o[[...left, right[k]].join(separator)] = 1;
          }
        }
      }
      return Object.keys(o);
    }
    const a = ['a', 'b', 'c', 'd'];
    const b = await getCombos(a);
    console.log(b);

    // (14) ['a', 'ab', 'ac', 'ad', 'abc', 'abd', 'abcd', 
    //       'b', 'bc', 'bd', 'bcd', 'c', 'cd', 'd']

This code splits the array into 2 sub arrays, left / right, then iterate over the right array to combine it with the left array. The left becomes bigger overtime, while the right becomes smaller. The result has only unique values.

Wellpreserved

Answer 14

I required a function to find all combinations so I converted this answer from PHP - https://mcmap.net/q/262861/-php-how-to-get-all-possible-combinations-of-1d-array-duplicate

Credit to abcde123483

function depthPicker(arr, tempString, collect) {
    if (tempString !== "") {
        collect.push(tempString);
    }

    for (let i = 0; i < arr.length; i++) {
        const arrCopy = [...arr];
        const elem = arrCopy.splice(i, 1)[0]; // removes and returns the i'th element
        if (arrCopy.length > 0) {
            depthPicker(arrCopy, tempString + " " + elem, collect);
        } else {
            collect.push(tempString + " " + elem);
        }
    }
}

const collect = [];
const array = ["A", "B", "C"];
depthPicker(array, "", collect);

console.log(collect);

Comprehensible

Answer 15

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)];
}

Vaulting

Answer 16

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]
  }, [])
}

Coupon