Given an array, how to generate all combinations of subset size k?
So given input = [1, 2, 3]
and k=2
this would return:
1 2
1 3
2 1
2 3
3 1
3 2
This is the closest to what I am looking for, but not quite: http://algorithms.tutorialhorizon.com/print-all-combinations-of-subset-of-size-k-from-given-array/
function subsetsOfSize(a, used, startIndex, currentSize, k) {
if (currentSize === k) {
for (var i = 0; i < a.length; i++) {
if (used[i])
console.log(a[i]);
}
console.log('-');
return;
}
if (startIndex === a.length)
return;
used[startIndex] = true;
subsetsOfSize(a, used, startIndex+1, currentSize+1, k);
used[startIndex] = false;
subsetsOfSize(a, used, startIndex+1, currentSize, k);
}
var input = [1,2,3];
subsetsOfSize(input, Array(input.length).fill(false), 0, 0, 2);
^ Missing results such as 2 1
, 3 1
, 3 2
, etc.
Secondly, I am not sure if I am naming this problem correctly because solutions to "all combinations of subset of size k" do not give the expected answer.
A recursive solution to find k-subset permutations (in pseudo-code):
kSubsetPermutations(partial, set, k) {
for (each element in set) {
if (k equals 1) {
store partial + element
}
else {
make copy of set
remove element from copy of set
recurse with (partial + element, copy of set, k - 1)
}
}
}
Here's a run-through for an example:
input: [a,b,c,d,e]
k: 3
partial = [], set = [a,b,c,d,e], k = 3
partial = [a], set = [b,c,d,e], k = 2
partial = [a,b], set = [c,d,e], k = 1 -> [a,b,c], [a,b,d], [a,b,e]
partial = [a,c], set = [b,d,e], k = 1 -> [a,c,b], [a,c,d], [a,c,e]
partial = [a,d], set = [b,c,e], k = 1 -> [a,d,b], [a,d,c], [a,d,e]
partial = [a,e], set = [b,c,d], k = 1 -> [a,e,b], [a,e,c], [a,e,d]
partial = [b], set = [a,c,d,e], k = 2
partial = [b,a], set = [c,d,e], k = 1 -> [b,a,c], [b,a,d], [b,a,e]
partial = [b,c], set = [a,d,e], k = 1 -> [b,c,a], [b,c,d], [b,c,e]
partial = [b,d], set = [a,c,e], k = 1 -> [b,d,a], [b,d,c], [b,d,e]
partial = [b,e], set = [a,c,d], k = 1 -> [b,e,a], [b,e,c], [b,e,d]
partial = [c], set = [a,b,d,e], k = 2
partial = [c,a], set = [b,d,e], k = 1 -> [c,a,b], [c,a,d], [c,a,e]
partial = [c,b], set = [a,d,e], k = 1 -> [c,b,a], [c,b,d], [c,b,e]
partial = [c,d], set = [a,b,e], k = 1 -> [c,d,a], [c,d,b], [c,d,e]
partial = [c,e], set = [a,b,d], k = 1 -> [c,e,a], [c,e,b], [c,e,d]
partial = [d], set = [a,b,c,e], k = 2
partial = [d,a], set = [b,c,e], k = 1 -> [d,a,b], [d,a,c], [d,a,e]
partial = [d,b], set = [a,c,e], k = 1 -> [d,b,a], [d,b,c], [d,b,e]
partial = [d,c], set = [a,b,e], k = 1 -> [d,c,a], [d,c,b], [d,c,e]
partial = [d,e], set = [a,b,c], k = 1 -> [d,e,a], [d,e,b], [d,e,c]
partial = [e], set = [a,b,c,d], k = 2
partial = [e,a], set = [b,c,d], k = 1 -> [e,a,b], [e,a,c], [e,a,d]
partial = [e,b], set = [a,c,d], k = 1 -> [e,b,a], [e,b,c], [e,b,d]
partial = [e,c], set = [a,b,d], k = 1 -> [e,c,a], [e,c,b], [e,c,d]
partial = [e,d], set = [a,b,c], k = 1 -> [e,d,a], [e,d,b], [e,d,c]
function kSubsetPermutations(set, k, partial) {
if (!partial) partial = []; // set default value on first call
for (var element in set) {
if (k > 1) {
var set_copy = set.slice(); // slice() creates copy of array
set_copy.splice(element, 1); // splice() removes element from array
kSubsetPermutations(set_copy, k - 1, partial.concat([set[element]]));
} // a.concat(b) appends b to copy of a
else document.write("[" + partial.concat([set[element]]) + "] ");
}
}
kSubsetPermutations([1,2,3,4,5], 3);
Instead of combinations, try permutations.
Try generating permutations, then resizing the array.
Here's it implemented, modified from here
var permArr = [],
usedChars = [];
function permute(input, k) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
var toadd = usedChars.slice(0,k);
if(!permArr.includes(toadd)) permArr.push(toadd); // resizing the returned array to size k
}
permute(input, k);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
console.log(JSON.stringify(permute([1, 2, 3], 2)));
You could take a generator function.
function* permutation(array, k, head = []) {
if (!k) {
yield head;
return;
};
for (let i = 0; i < array.length; i++) {
yield* permutation(array.filter((_, j) => j !== i), k - 1, [...head, array[i]]);
}
}
// example 1
const p = permutation([1, 2, 3, 4, 5, 6], 4);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
// example 2
[...permutation([1, 2, 3, 4], 3)].forEach(a => console.log(...a));
.as-console-wrapper { max-height: 100% !important; top: 0; }