JavaScript functions to calculate combinations of elements in Array.

combinations.js

/**
 * Copyright 2012 Akseli Palén.
 * Created 2012-07-15.
 * Licensed under the MIT license.
 * 
 * <license>
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files
 * (the "Software"), to deal in the Software without restriction,
 * including without limitation the rights to use, copy, modify, merge,
 * publish, distribute, sublicense, and/or sell copies of the Software,
 * and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * </lisence>
 * 
 * Implements functions to calculate combinations of elements in JS Arrays.
 * 
 * Functions:
 *   k_combinations(set, k) -- Return all k-sized combinations in a set
 *   combinations(set) -- Return all combinations of the set
 */


/**
 * K-combinations
 * 
 * Get k-sized combinations of elements in a set.
 * 
 * Usage:
 *   k_combinations(set, k)
 * 
 * Parameters:
 *   set: Array of objects of any type. They are treated as unique.
 *   k: size of combinations to search for.
 * 
 * Return:
 *   Array of found combinations, size of a combination is k.
 * 
 * Examples:
 * 
 *   k_combinations([1, 2, 3], 1)
 *   -> [[1], [2], [3]]
 * 
 *   k_combinations([1, 2, 3], 2)
 *   -> [[1,2], [1,3], [2, 3]
 * 
 *   k_combinations([1, 2, 3], 3)
 *   -> [[1, 2, 3]]
 * 
 *   k_combinations([1, 2, 3], 4)
 *   -> []
 * 
 *   k_combinations([1, 2, 3], 0)
 *   -> []
 * 
 *   k_combinations([1, 2, 3], -1)
 *   -> []
 * 
 *   k_combinations([], 0)
 *   -> []
 */
function k_combinations(set, k) {
	var i, j, combs, head, tailcombs;
	
	// There is no way to take e.g. sets of 5 elements from
	// a set of 4.
	if (k > set.length || k <= 0) {
		return [];
	}
	
	// K-sized set has only one K-sized subset.
	if (k == set.length) {
		return [set];
	}
	
	// There is N 1-sized subsets in a N-sized set.
	if (k == 1) {
		combs = [];
		for (i = 0; i < set.length; i++) {
			combs.push([set[i]]);
		}
		return combs;
	}
	
	// Assert {1 < k < set.length}
	
	// Algorithm description:
	// To get k-combinations of a set, we want to join each element
	// with all (k-1)-combinations of the other elements. The set of
	// these k-sized sets would be the desired result. However, as we
	// represent sets with lists, we need to take duplicates into
	// account. To avoid producing duplicates and also unnecessary
	// computing, we use the following approach: each element i
	// divides the list into three: the preceding elements, the
	// current element i, and the subsequent elements. For the first
	// element, the list of preceding elements is empty. For element i,
	// we compute the (k-1)-computations of the subsequent elements,
	// join each with the element i, and store the joined to the set of
	// computed k-combinations. We do not need to take the preceding
	// elements into account, because they have already been the i:th
	// element so they are already computed and stored. When the length
	// of the subsequent list drops below (k-1), we cannot find any
	// (k-1)-combs, hence the upper limit for the iteration:
	combs = [];
	for (i = 0; i < set.length - k + 1; i++) {
		// head is a list that includes only our current element.
		head = set.slice(i, i + 1);
		// We take smaller combinations from the subsequent elements
		tailcombs = k_combinations(set.slice(i + 1), k - 1);
		// For each (k-1)-combination we join it with the current
		// and store it to the set of k-combinations.
		for (j = 0; j < tailcombs.length; j++) {
			combs.push(head.concat(tailcombs[j]));
		}
	}
	return combs;
}


/**
 * Combinations
 * 
 * Get all possible combinations of elements in a set.
 * 
 * Usage:
 *   combinations(set)
 * 
 * Examples:
 * 
 *   combinations([1, 2, 3])
 *   -> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
 * 
 *   combinations([1])
 *   -> [[1]]
 */
function combinations(set) {
	var k, i, combs, k_combs;
	combs = [];
	
	// Calculate all non-empty k-combinations
	for (k = 1; k <= set.length; k++) {
		k_combs = k_combinations(set, k);
		for (i = 0; i < k_combs.length; i++) {
			combs.push(k_combs[i]);
		}
	}
	return combs;
}

I think it doesnt work for 4 elements

It works great. Thanks. I tested it for 4 elements as well and it works great. Thanks.

So it works but only generates combinations in the same original order - how could you get all combinations in any order?

thanks a lot

@chrisgoddard you're looking for a permutations function, not a combinations function.

@chrisgoddard you can run each combination through a permutation algorithm with something like this: https://github.com/eriksank/permutation-engine
Or, use permutation/combination engine, like this one:
https://github.com/dankogai/js-combinatorics

Is the above gist available on npm somewhere? I want to use it in my library, right now I've just copy & pasted it.

@danbars Thanks for the links. +1

Does Not work for this set "ababb" it repeats elements and also "abbba", "babab" are missing

@foluis all member elements must be considered unique in order to form a set mathematically

possible combination of 1, 2, 3 are following,may be i am wrong

[1], [2], [3], [1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2], [1, 2, 3], [3, 2, 1]

Thanks a lot!

Thanks!

@imVinayPandya Looks like he is using N choose K which should only return unique combinations. Such as 1,2 and 2,1 are the same. Also, you are setting the number of members for the k combination. Thus this will only return single member combinations, or double member combinations or triple member combinations etc etc etc.

thanks!

Here is a short hand version using underscore and some es6 syntax for readability

"use strict";
//https://gist.github.com/axelpale/3118596

const _ = require('underscore');

const elemTransform = elem => [elem];
const tailcombPush = (combs, elem) => tailcomb => combs.push([elem, ...tailcomb]);
const k_combPush = combs => k_komb => combs.push(k_komb);

function k_combinations(set, k) {
  const setLen = set.length;
  if (k > setLen || k <= 0) {
    return [];
  }
  if (k === setLen) {
    return [set];
  }
  if (k === 1) {
    return _.map(set, elemTransform);
  }
  const combs = [];
  for (let i = 0; i < setLen - k + 1; i++) {
    _.each(k_combinations(set.slice(i + 1), k - 1), tailcombPush(combs, set[i]));
  }
  return combs;
}

function combinations(set) {
  const combs = [];
  for (let k = 1; k <= set.length; k++) {
    _.each(k_combinations(set, k), k_combPush(combs));
  }
  return combs;
}

module.exports = {
  k_combinations,
  combinations
};

Here's an es6 version

const k_combinations = (set, k) => {                                            
  if (k > set.length || k <= 0) {                                               
    return []                                                                   
  }                                                                             
  if (k === set.length) {                                                       
    return [set]                                                    
  }                                                                             
  const combs = []                                                              
  if (k === 1) {                                                                
    for (let i = 0; i < set.length; i++) {                                      
      combs.push([set[i]])                                                      
    }                                                                           
    return combs                                                                
  }                                                                             
  for (let i = 0; i < set.length - k + 1; i++) {                                
    const head = set.slice(i, i + 1)                                            
    const tailcombs = k_combinations(set.slice(i + 1), k - 1)              
    for (let j = 0; j < tailcombs.length; j++) {                                
      combs.push(head.concat(tailcombs[j]))                                     
    }                                                                           
  }                                                                             
  return combs                                                                  
}                                                                               
                                                                                
const combinations = (set) => {                                                 
  const combs = [];                                                             
  for (let k = 1; k <= set.length; k++) {                                       
    const k_combs = k_combinations(set, k)                                      
    for (let i = 0; i < k_combs.length; i++) {                                  
      combs.push(k_combs[i])                                                    
    }                                                                           
  }                                                                             
  return combs                                                                  
}

ES6 version:

const k_combinations = (set, k) => {
  if (k > set.length || k <= 0) {
    return []
  }
  
  if (k == set.length) {
    return [set]
  }
  
  if (k == 1) {
    return set.reduce((acc, cur) => [...acc, [cur]], [])
  }
  
  let combs = [], tail_combs = []
  
  for (let i = 0; i <= set.length - k + 1; i++) {
    tail_combs = k_combinations(set.slice(i + 1), k - 1)
    for (let j = 0; j < tail_combs.length; j++) {
      combs.push([set[i], ...tail_combs[j]])
    }
  }
  
  return combs
}

const combinations = set => {
  return set.reduce((acc, cur, idx) => [...acc, ...k_combinations(set, idx + 1)], [])
}

And here is a (generic) typescript version, based on the ES6 version by @luispaulorsl:

export const k_combinations = <T>(set: T[], k: number) => {
    if (k > set.length || k <= 0) {
        return [];
    }

    if (k === set.length) {
        return [set];
    }

    if (k === 1) {
        return set.reduce((acc, cur) => [...acc, [cur]], [] as T[][]);
    }

    const combs = [] as T[][];
    let tail_combs = [];

    for (let i = 0; i <= set.length - k + 1; i++) {
        tail_combs = k_combinations(set.slice(i + 1), k - 1);
        for (let j = 0; j < tail_combs.length; j++) {
            combs.push([set[i], ...tail_combs[j]]);
        }
    }

    return combs;
};

export const combinations = <T>(set: T[]) => {
    return set.reduce((acc, _cur, idx) => [...acc, ...k_combinations(set, idx + 1)], [] as T[][]);
};

Thanks. Here is just a little addition to @luispaulorsl code to be able to limit the range of the combinations with a min and max length.

// REF: https://gist.github.com/axelpale/3118596#gistcomment-2751797

const k_combinations = (set, k) => {
  if (k > set.length || k <= 0) {
    return [];
  }

  if (k === set.length) {
    return [set];
  }

  if (k === 1) {
    return set.reduce((acc, cur) => [...acc, [cur]], []);
  }

  let combs = [],
    tail_combs = [];

  for (let i = 0; i <= set.length - k + 1; i++) {
    tail_combs = k_combinations(set.slice(i + 1), k - 1);
    for (let j = 0; j < tail_combs.length; j++) {
      combs.push([set[i], ...tail_combs[j]]);
    }
  }

  return combs;
};

const combinations = (set, min, max) => {
  const arr = Array.from({ length: max - min + 1 }, (_, i) => i + min);
  return arr.reduce((acc, cur, idx) => {
    return [...acc, ...k_combinations(set, cur)];
  }, []);
};

typescript version

export function combinations<T>(set: Array<T>, k: number): Array<Array<T>> {
  if (k > set.length || k <= 0) return [];
  if (k === set.length) return [set];

  return set.reduce((p, c, i) => {
    combinations(set.slice(i + 1), k - 1)
      .forEach(tailArray => p.push([c].concat(tailArray)));

    return p;
  }, []);
}

I wish one of these versions could yield instead of generating and returning the whole thing.

mine was a little too short:

function combinations<T>(set: Array<T>, k: number): Array<Array<T>> {
  // src: https://gist.github.com/axelpale/3118596
  if (k > set.length || k <= 0) return []
  if (k === set.length) return [set]
  if (k === 1) return set.map(x => [x])

  return set.reduce((p, c, i) => {
    combinations(set.slice(i + 1), k - 1).forEach(tailArray =>
      p.push([c].concat(tailArray)),
    )

    return p
  }, [])
}

@tan14142 interesting thought.. something kinda like this?

function* combinations<T>(
  set: Array<T>,
  k: number,
): Generator<Array<T>, Array<T>, undefined> {
  if (k > set.length || k <= 0) yield []
  if (k === 1) yield* set.map(x => [x])

  for (const i in set) {
    const x = set[i]
    for (const next of combinations<T>(set.slice(+i + 1), k - 1)) {
      yield [x].concat(next)
    }
  }
  return
}

that's almost not legible to me .. prettier is .. much less pretty with typescript. here's the js version:

function* combinations(set, k) {
  if (k > set.length || k <= 0) yield []
  if (k === 1) yield* set.map(x => [x])

  for (let i in set) {
    const x = set[i]
    for (const next of combos(set.slice(+i + 1), k - 1)) {
      yield [x].concat(next)
    }
  }
}

producing for example:

JSON.stringify([...combinations([1,2,3,4], 2)])
'[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]'
JSON.stringify([...combinations([1,2,3,4], 3)])
'[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]'

you could verify that it works like so:

function* combinations(set, k) {
console.log('foo')
  if (k > set.length || k <= 0) yield []
  if (k === 1) yield* set.map(x => [x])

    for (let i in set) {
      const x = set[i]
      for (const next of combinations(set.slice(+i + 1), k - 1)) {
        yield [x].concat(next)
      }
    }
}
function* take( num, iter ) {
  let item = iter.next()
  for( let index = 0; index < num && !item.done ; index++) {
    yield item.value
    item = iter.next()
  }
}

JSON.stringify([...take(3,combinations([1,2,3,4], 2))])
VM35607:2 foo
VM35607:2 foo
VM35607:2 foo
'[[1,2],[1,3],[1,4]]'

I felt clever but looking at larger examples like 10 choose 4 .. my generator is returning too long of entries sometimes

I got some help debugging that:

function* combinations(set, k) {
  if (k > set.length || k <= 0) {
    return
  }
  if (k === set.length) {
    yield set
    return
  }
  if (k === 1) {
    yield* set.map(x => [x])
    return
  }

  for (let i=0,lim=set.length; i<lim; i++) {
    for (const next of combinations(set.slice(i + 1), k - 1)) {
      yield [set[i]].concat(next)
    }
  }
  return
}

Bergi actually suggested a slightly tighter solution than we'd covered in this gist:

function* combinations(set, k) {
  if (k >= 0 && k <= set.length) {
    if (k == 0) {
      yield [];
    } else {
      for (const [i, v] of set.entries())
        for (const next of combinations(set.slice(i + 1), k - 1)) {
          yield [v, ...next];
        }
      }
    }
  }
}

Here's a generator version in typescript that doesn't use recursion:

function* combinations<T>(arr: T[], size: number): Generator<T[], void, unknown> {
    if (size < 0 || arr.length < size)
        return; // invalid parameters, no combinations possible

    // generate the initial combination indices
    const combIndices: number[] = Array.from(Array(size).keys());

    while (true)
    {
        yield combIndices.map(x => arr[x]);

        // find first index to update
        let indexToUpdate = size - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= arr.length - size + indexToUpdate)
            indexToUpdate--;

        if (indexToUpdate < 0)
            return; 

        // update combination indices
        for (let combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < size; indexToUpdate++, combIndex++)
            combIndices[indexToUpdate] = combIndex;
    }
}

I wanted a non-recursive version so I didn't have to worry about tail recursion and call stacks for potentially large power sets. However, I haven't thought about these limitations too deeply or actually tested its performance vs the solutions above.
This is based on someone's C# answer from 2015 here.