JRS: In article <
[email protected]>,
dated Sun, 1 Oct 2006 01:33:36 remote, seen in
news:comp.lang.javascript said:
I need to iterate over combinations of n array elements taken r at a
time. Because the value of r may vary quite a bit between program
invocations, I'd like to avoid simply hardcoding r loops. I assume the
best way to do this would be either using closures or creating some
sort of iterator class.
Any guidance on how to get started?
See <URL:
http://www.merlyn.demon.co.uk/js-misc0.htm#CP>.
Combinations are generated recursively, though AIUI any recursive
algorithm can be expressed iteratively.
function Comb(n, a, z, D) { // List combinations - D starts empty
if (n==0) { D[D.length] = z ; return }
for (var j=0 ; j < a.length ; j++)
Comb(n-1, a.slice(j+1), z+a[j], D)
return }
function TestComb() { var S = ["a","b","c","d"], D, k
document.writeln("TestComb() :")
for (k=0 ; k <= S.length ; k++) {
D = [] ; Comb(k, S, "", D)
document.writeln("Comb(", k, ") = ", D) } }
document.writeln("<pre>")
TestComb()
document.writeln("<\/pre>")
gives:-
TestComb() :
Comb(0) =
Comb(1) = a,b,c,d
Comb(2) = ab,ac,ad,bc,bd,cd
Comb(3) = abc,abd,acd,bcd
Comb(4) = abcd
So :-
D = [] ; Comb(2, S = ["a","b","c","d"], "", D) ;
gives D as ['ab', 'ac', 'ad', 'bc', 'bd', 'cd'] .
There should be a way of adapting that so that each element of array D
is not a string but an array of combinations of the elements of the
parameter array. Change f to take that array as a parameter, using
within it the array called arguments - and you might be more or less
there.
It's a good idea to read the newsgroup and its FAQ. See below.