Skip to content

Instantly share code, notes, and snippets.

@marselester
Created August 15, 2013 06:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save marselester/6238787 to your computer and use it in GitHub Desktop.
Save marselester/6238787 to your computer and use it in GitHub Desktop.
I did it as a test task. Given a set of integers S and a positive integer L, create a function that generates all the possible subsets of S of length L. Example: if S={1, 2, 3} and L=2, then subsets(S, L) is {1, 2}, {1, 3}, {2, 3}.
function range(n) {
list = [];
for (var i = 0; i < n; i++) {
list[i] = i;
}
return list;
}
function show_items_by_indices(source_set, indices) {
for (var i = 0; i < indices.length; i++) {
document.write(source_set[indices[i]]);
}
document.write('<br/>');
}
function combinations(source_set, len_subseq) {
var total = source_set.length;
if (len_subseq > total) {
return;
}
var indices = range(len_subseq);
// First len_subseq elements from source_set.
show_items_by_indices(source_set, indices);
while (true) {
var was_break = false;
for (var i = 0; i < len_subseq; i++) {
// It is a reversed index. "-1" is a zero numbering correction.
var ri = len_subseq - i - 1;
if (indices[ri] != (ri + total - len_subseq)) {
was_break = true;
break;
}
}
if ( ! was_break) {
return;
}
indices[ri]++;
for (var i = ri + 1; i < len_subseq; i++) {
indices[i] = indices[i - 1] + 1
}
show_items_by_indices(source_set, indices);
}
}
combinations([1, 2, 3], 2);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment