Created
August 15, 2013 06:48
-
-
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}.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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