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

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

Answers:

Answer

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

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

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

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

Try this: https://jsfiddle.net/e2dLa9v6/

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

for(var i=0;i<array.length-1;i++){
    for(var j=i+1;j<array.length;j++){
    result.push(array[i]+" "+array[j]);
  }
}
for(var i=0;i<result.length;i++){
    alert(result[i]);
}
Answer

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

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:

enter image description here

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

Answer

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

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

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.