Jump to content
  • Advertisement
Sign in to follow this  
Zomis

Chossing a combination of the ones possible, return the members

This topic is 3940 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
Advertisement
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
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" ?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!