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

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

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

Solution 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.

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

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

View more solutions

Comments

[SrAxi]

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

[Phrogz]

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

[trincot]

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.

[Simas Joneliunas]

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

[JxDarkAngel]

Thank you! for your suggestion

[Abdo Rabah]

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

[Velidan]

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

[Yusuf Khan]

can you mention the time complexity of this algorithm ?

[Erik Vullings]

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

[user3658510]

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

[user3658510]

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

[user3658510]

Functional programming inspired.

[user3658510]

Working algorithm extensively explained and with very explicit naming convention.

[user3658510]

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

[Serkan KONAKCI]

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

[PirateApp]

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]

[PirateApp]

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

[Wish]

Those are permutations, not combinations

[Cristian M.]

Great script, thanks!

[PRANAV]

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....

[Shiroy]

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'

[Ehsan88]

This actually gives the permutations with repetition

[cervezas]

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