-
-
Save axelpale/3118596 to your computer and use it in GitHub Desktop.
/** | |
* 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; | |
} |
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.
I wish one of these versions could yield instead of generating and returning the whole thing.