1. ## 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

2. this should really be in the general board

3. Ps, no i cant do it, but 6/49 makes me think of 14 million

4. ## 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

5. where
n = number of items
r = how many are being chosen

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

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

7. 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];

}```

8. ## 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

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