Sign in to follow this  

Chossing a combination of the ones possible, return the members

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this