# Combinations, lotto, 6/49

• 12-06-2002
Robert
Combinations, lotto, 6/49
Hello folks

Haven't heard from you for days...:-) Well, is my fault, but now I'm back.

Of course, another issue. Been some time I finished school, so I completly forgot (if ever attended) the combinations (math) lesson, you know, you are given 8 buddyes, you have to make X teams choosing two of them. How many combinations (teams) could you have? The same applyes to 6/49 (which is my interest right now, a friend of mine called me to make him an applications that would do the listing for him).

If anyone has encountered and solved this somehow, please let me know. I don't even know where to start from

Regards
Robert
• 12-06-2002
-Xp-
this should really be in the general board
• 12-06-2002
-Xp-
Ps, no i cant do it, but 6/49 makes me think of 14 million
• 12-06-2002
Robert
Do you think this is not the place?
Do you think this is not the place for this? I need something in C+, and you are right, I don't need to list ALL the combinations, there should be, let's say, 6 numbers and 5 chosen, or 7 with 5 chosen.
Well, no second thoughts?

Robert
• 12-06-2002
beege31337
where
n = number of items
r = how many are being chosen

C(n,r) = n! / ((n-r)!r!)
• 12-06-2002
Robert
Quote:

Originally posted by beege31337
where
n = number of items
r = how many are being chosen

C(n,r) = n! / ((n-r)!r!)

Yes, I know this, what I need is the source that would generate the combinations itself.
What I discovered is that the combinations are the counting in binary (ie 10010) from 0 to 2 ^ n, where the number of 1's = n - r.
So I thought using the count in binary, eliminate the unnecessary numbers, and apply the pattern (kinda XOR) to the numbers 'string'. There will be left only the numbers I am looking for, so there's the listing.
Any other idea?

Robert
• 12-06-2002
beege31337
So you want to pick, say, 6 numbers out of 1 to 40 (im not sure how 6/49 works because im from the US)?

you could put the numbers in some sort of container,

choose one randomly

remove that number

and repeat

So for example with and array ( not perfect code)
Code:

```int array[40]; //fill the array for(int i=0;i<40;i++)array[i]=i+1; //now get the numbers int index; int num_elements = 40; for(int i = 6; i > 0; i--) {     //find a random index     index = randomInt( 0 , num_elements-1 );     //output the number     cout << array[index] <<endl;     //move the last number in the array to the spot where index was     //and decrement num_elements     array[index] =array[--num_elements]; }```
• 12-06-2002
Robert
Well, not quite
6/49 means there are 49 numbers at all (1 to 49), and they pick 6 numbers from them. You can play how many combinations you like, made of 6, 5 ,4 numbers, your pick.
Say you play 7 numbers [n], in combinations of 5 [r] (1, 2, 3, 4, 5, 6, 7 for easy reading), your combinations would look like this:
1 2 3 4 5 _ _
1 2 3 4 _ 6 _
1 2 3 4 _ _ 7
1 2 3 _ 5 6 _
1 2 3 _ 5 _ 7
1 2 3 _ _ 6 7
1 2 _ 4 5 6 _
1 2 _ 4 5 _ 7
1 2 _ 4 _ 6 7
1 2 _ _ 5 6 7 and so on...

If you take a careful look at this underscored presentation (ola!), ignore the figures but take into account underscores itself, they are the binary count from 0 to 2^n, 7 in this case, but only the numbers that have r 1's in it!(here 2 1's)
Do you see this?
So what I meant is to continuously count from 0 to 2^n, eliminate all the binary numbers that have more or less 1's than r (2 here), and then, using the binary array like a mask, eliminate from the array of numbers n ones that match the position of 1's. I'll get the above picture.
This is what I mastered knoking my head off to find a solution for my friend's listing.
What do you say?
(well, do I make any sense here?)
I was looking the web for something like this, but didn't find anything that the theory. If you know an easyer way, please let me know.

Robert
• 12-06-2002
beege31337
Here I wrote some code that should help get you started

Code:

``` #include<iostream> #include<unistd.h> using namespace std; int pow2(int N) {         if(N==0) return 1;         if(N==1)return 2;         return 2 * pow2(N-1); } int main(){         int n;         cout << "Enter n:";         cin >> n;         int r;         cout << "Enter r:";         cin >> r;         int *num_array = new int[n];         //fill the array         for(int i=1;i<=n;i++){                 cout << "Enter Number " << i <<" :";                 cin >> num_array[i-1];         }         //this array will hold the number of ones         //in the binary representation of it's index         int *howManyOnesArray = new int[pow2(n)];         //fill the array         int temp;         for(int i=0;i<pow2(n);i++) {                 temp = i;//this number will be stripped apart                         //to find the binary ones in it                 for(int x=1;x<=8;x++){                         if(temp % pow2(x) != 0){                                 howManyOnesArray[i]++;                                 temp -= pow2(x-1);                         }                 }         }         //now list the integers whos binary representation         //has r ones         for(int i=0;i<pow2(n);i++)                 if(howManyOnesArray[i]==r)                         cout<<i<<" has " << howManyOnesArray[i] << " ones."<<endl; }```
It takes in n and r and then outputs the numbers which have r 1's in their binary form.

The program currently is only set to work up to 255, or 8 binary digits, but i think that was all that you needed