Iterate over array element combinations

J

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.
 
J

Jacob JKW

VK said:
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.com/group/comp.lang.javascript/browse_frm/thread/65f35a3a759cd883>

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....
 
V

VK

Jacob said:
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(subset.push(myArray[j]));
}

}

}

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

Dr John Stockton

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.
 
J

Jacob JKW

VK said:
Jacob said:
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(subset.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. :)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top