Iterate over array element combinations

[Jacob JKW]

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?
Thanks,
Jacob.

[VK]

I need to iterate over combinations of n array elements taken r at a

time.

The algorithm description is not fully clear. If you are trying to
implement a sort of Shannon's clairvoyant, you may find interesting the
thread "Looping through variable number of arrays variable times?" at
<http://groups.google.c om/group/comp.lang.javas cript/browse_frm/thread/65f35a3a759cd88 3>

If not then sorry for a wrong guess, more details could help.

[Jacob JKW]

VK wrote:

I need to iterate over combinations of n array elements taken r at a
time.

The algorithm description is not fully clear. If you are trying to
implement a sort of Shannon's clairvoyant, you may find interesting the
thread "Looping through variable number of arrays variable times?" at
<http://groups.google.c om/group/comp.lang.javas cript/browse_frm/thread/65f35a3a759cd88 3>

If not then sorry for a wrong guess, more details could help.

You're right. I really didn;t explain this very well at all.

I have an array of n floats. What I need to do is calculate a function
of the elements of every subset of n containing exactly r elements
(actually it's r or fewer, but for the sake of simplicity let's just
say exactly r) and then figure the sum of the functions

So for example given array = (a, b, c, d):

For r = 2 I'd be looking for:
f(a,b) + f(a,c) + f(a,d) + f(b,c) + f(b,d) + f(c,d)

and for r=3 I'd be looking for:
f(a,b,c) + f(a,b,d) + f(a,c,d) + f(b,c,d)
etc....

[VK]

Jacob JKW wrote:

I have an array of n floats. What I need to do is calculate a function
of the elements of every subset of n containing exactly r elements
(actually it's r or fewer, but for the sake of simplicity let's just
say exactly r) and then figure the sum of the functions

So for example given array = (a, b, c, d):

For r = 2 I'd be looking for:
f(a,b) + f(a,c) + f(a,d) + f(b,c) + f(b,d) + f(c,d)

and for r=3 I'd be looking for:
f(a,b,c) + f(a,b,d) + f(a,c,d) + f(b,c,d)

etc....

I see now... I guess the most helpful array method here would be
slice(lbound, ubound)

function iterator(r) {

var subset = new Array();
var len = myArray.length;
var lim = len - r;

for (var i=0; i<lim; i++) {
subset = myArray.slice(i , r-1);

for (var j=r; j<len; j++) {
methodCall(subs et.push(myArray[j]));
}

}

}

I did not check it for working, just some thoughts - I feel like I lost
some +/- 1 for indexes

[Dr John Stockton]

JRS: In article <11************ **********@k70g 2000cwa.googleg roups.com>,
dated Sun, 1 Oct 2006 01:33:36 remote, seen in
news:comp.lang. javascript, Jacob JKW <ja******@yahoo .composted :

>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.demo n.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.writel n("TestComb() :")
for (k=0 ; k <= S.length ; k++) {
D = [] ; Comb(k, S, "", D)
document.writel n("Comb(", k, ") = ", D) } }

document.writel n("<pre>")
TestComb()
document.writel n("<\/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.
--
© John Stockton, Surrey, UK. ?@merlyn.demon. co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.c om/faq/>? JL/RC: FAQ of news:comp.lang. javascript
<URL:http://www.merlyn.demo n.co.uk/js-index.htmjscr maths, dates, sources.
<URL:http://www.merlyn.demo n.co.uk/TP/BP/Delphi/jscr/&c, FAQ items, links.

[Jacob JKW]

Dr John Stockton wrote:

JRS: In article <11************ **********@k70g 2000cwa.googleg roups.com>,
dated Sun, 1 Oct 2006 01:33:36 remote, seen in
news:comp.lang. javascript, Jacob JKW <ja******@yahoo .composted :

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.demo n.co.uk/js-misc0.htm#CP>.
Combinations are generated recursively, though AIUI any recursive
algorithm can be expressed iteratively.

<snip code sample from http://www.merlyn.demo n.co.uk/js-misc0.htm#CP>
This is perfect!. Thank you very much. :)

Jacob

[Jacob JKW]

VK wrote:

Jacob JKW wrote:

I have an array of n floats. What I need to do is calculate a function
of the elements of every subset of n containing exactly r elements
(actually it's r or fewer, but for the sake of simplicity let's just
say exactly r) and then figure the sum of the functions

So for example given array = (a, b, c, d):

For r = 2 I'd be looking for:
f(a,b) + f(a,c) + f(a,d) + f(b,c) + f(b,d) + f(c,d)

and for r=3 I'd be looking for:
f(a,b,c) + f(a,b,d) + f(a,c,d) + f(b,c,d)

etc....

I see now... I guess the most helpful array method here would be
slice(lbound, ubound)

function iterator(r) {

var subset = new Array();
var len = myArray.length;
var lim = len - r;

for (var i=0; i<lim; i++) {
subset = myArray.slice(i , r-1);

for (var j=r; j<len; j++) {
methodCall(subs et.push(myArray[j]));
}

}

}

I did not check it for working, just some thoughts - I feel like I lost
some +/- 1 for indexes

TYhis looks rather good as well.

For no real reason I decided to move forward with John's suggestion
above. But thanks anyway for your help on this. Highly appreciated. :)

[Dr John Stockton]

JRS: In article <11************ *********@k70g2 000cwa.googlegr oups.com>,
dated Mon, 2 Oct 2006 07:25:51 remote, seen in
news:comp.lang. javascript, Jacob JKW <ja******@yahoo .composted :

>
<snip code sample from http://www.merlyn.demo n.co.uk/js-misc0.htm#CP>
This is perfect!. Thank you very much. :)

It was merely OK; I've improved it.

--
© John Stockton, Surrey, UK. ?@merlyn.demon. co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.c om/faq/>? JL/RC: FAQ of news:comp.lang. javascript
<URL:http://www.merlyn.demo n.co.uk/js-index.htmjscr maths, dates, sources.
<URL:http://www.merlyn.demo n.co.uk/TP/BP/Delphi/jscr/&c, FAQ items, links.