Chossing a combination of the ones possible, return the members

This topic is 4030 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

"A combination is a set of objects in which order is not important." http://www.regentsprep.org/Regents/math/combin/Lcomb.htm Let's say that I have x objects, and I want to choose y of these objects. How many combinations can I get? Answer can be found on the site above, it's equal to: nCr(x, y), which translated into a programming language would be:
function nPr(n, r) {
result = n;
for (var i=n-1;i>n-r;n--)
result = result * i;
}

function nCr(n, r) {
nPr(n, r) / nPr(r, r);
// nPr(r, r) == r factorial (r!)
}
OK, so now we know how many combinations we can make out of these y of x objects. Now we want to find combination number z. How to do this? To show an example of what I mean, take a look at this function, and the explanations below it:
function nCr_combo(n, r, z: int, arr: Array): Array {
var combos = nCr(n, r);
if (x > combos) return null;// Invalid combination number
if (x <= 0) return null;// Invalid combination number
// pick correct elements from array, depending on the value of x
}
So let's say we have the array arr = [a, b, c, d] And nCr(arr.length, 2) returns 4*3 / 2*1 = 6; // we have 4 items, we choose two of them Then nCr_combo(arr.length, 2, x, arr) equals, depending on the value of x: 1: ab 2: ac 3: ad 4: bc 5: bd 6: cd a found in 1,2,3 b found in 1,4,5 c found in 2,4,6 d found in 3,5,6 So if I call nCr_combo(arr.length, 2, 4, [a,b,c,d]) then it should give me an array with the 2 items [b, c]. (As the list above says, "4: bc"). And for another array, arr = [a, b, c, d] And we want three items: nCr(arr.length, 3) = 4*3*2 / 3*2*1 = 4;// 4 combinations nCr_combo(arr.length, 3, x, arr) = 1: abc 2: abd 3: acd 4: bcd a found in 1,2,3 b found in 1,2,4 c found in 1,3,4 d found in 2,3,4 My problem is: How to assign the correct items to the array to be returned? Code in any language is accepted (the targeting language will be Flash, ActionScript 3.0). Any mathematic thoughts about how to know which items to return are also welcome.

Share on other sites
Pseudocode:

// The number of subsets of size P out of {1 ... N}
NCR(P,N)

// to select the K-th subset of size P out of integers {1 ... N}
SELECT(K,P,N) :
assert P ≥ 0 and P ≤ N
if P = 0
assert K = 1
return {}
else if P = N
assert K = 1
return {1 ... N}
else if K ≤ NCR(P,N-1)
return SELECT(K,P,N-1)
else
R := SELECT(K-NCR(P,N-1),P-1,N-1)
return UNION(R,{P})

Share on other sites
Thanks a lot for your code, ToohrVyk, I had some problems with the implementation but they're solved now. (All that's left is using an array of objects instead of plain numbers, but I think that isn't too much problem).

Here's my implementation, ActionScript 3.0 (Flash) code
function nCr(n, r: int): int {
return nPr(n, r) / nPr(r, r);
}

function nPr(n, r: int): int {
var res = n;
for (var i=n-1;i>n-r;i--)
res = res * i;
return res;
}

function ncrcombo2(x, r: int, arr: int): Array {
if ((r < 0) || (r > arr)) return null;
if (r == 0) {
if (x == 1) return new Array();
else return new Array();// failure
}
else if (r == arr) {
var a = new Array();
for (var i=1;i<=arr;i++) a.push(i);
return a;
}
else if (x <= nCr(arr-1, r)) {
return ncrcombo2(x, r, arr-1);
}
else {
var o = ncrcombo2(x-nCr(arr-1, r), r-1, arr-1);
o.push(arr);
return o;
}
}

var r = 3;
var n = 5;
for (var i=1;i<=nCr(n, r);i++)
trace(ncrcombo2(i, r, n));

gives:
1,2,3
1,2,4
1,3,4
2,3,4
1,2,5
1,3,5
2,3,5
1,4,5
2,4,5
3,4,5

The combinations wasn't in the order I expected, but since they're combinations, the order is not important ;)

Share on other sites
This isn't so important, but it would be nice if someone could help me with it.

I'm trying to make the above function work with an array parameter instead of an "arr: int" parameter.

This is my implementation attempt.
function ncrcombo3(x, r: int, arr: Array): Array {
if ((r < 0) || (r > arr.length)) return null;
if (r == 0) {
trace("Mode 0");
if (x == 1) return new Array();
else return new Array();// failure
}
else if (r == arr.length) {
trace("Mode 1");
return arr.slice();// All are included in solutions
}
else if (x <= nCr(arr.length-1, r)) {
trace("Mode 2");
return ncrcombo3(x, r, arr.slice(0, arr.length-2));
}
else {
trace("Mode 3");
var o = ncrcombo3(x-nCr(arr.length-1, r), r-1, arr.slice(0, arr.length-2));
o.push(arr);
return o;
}
}

var n = 4;
var r = 2;
for (var i=1;i<=nCr(n, r);i++)
trace(ncrcombo3(i, r, new Array('a','b','c','d')));

And here's the output:
Mode 2
Mode 1
a,b
Mode 2
Mode 1
a,b
Mode 2
Mode 1
a,b
Mode 3
Mode 2
TypeError: Error #1009: Cannot access a property or method of a null object reference.
at flags_fla::MainTimeline/ncrcombo3()
at flags_fla::MainTimeline/myfla::frame1()

So first of all: The combination result seems to always be the same
And secondly: The TypeError :/

Share on other sites
I'm not familiar with ActionScript, but the code:
Quote:
 arr.slice(0, arr.length-2)

Makes me feel uneasy. Shouldn't that be "-1" instead of "-2" ?

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 14
• Forum Statistics

• Total Topics
632961
• Total Posts
3009488
• Who's Online (See full list)

There are no registered users currently online

×