Thread: Combinations, lotto, 6/49

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    30

    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. #2
    Registered User -Xp-'s Avatar
    Join Date
    Nov 2002
    Posts
    28
    this should really be in the general board
    No I DIDN'T steal my name from Misro$ofts OS, it's pure coincidence.

    The lines around my name (-) are only there because i needed a name over the 3 character minimum letter limit

  3. #3
    Registered User -Xp-'s Avatar
    Join Date
    Nov 2002
    Posts
    28
    Ps, no i cant do it, but 6/49 makes me think of 14 million
    No I DIDN'T steal my name from Misro$ofts OS, it's pure coincidence.

    The lines around my name (-) are only there because i needed a name over the 3 character minimum letter limit

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    30

    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. #5
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    where
    n = number of items
    r = how many are being chosen

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

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    30
    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. #7
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    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. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    30

    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. #9
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Combinations
    By Cmuppet in forum C Programming
    Replies: 6
    Last Post: 10-19-2004, 07:39 AM
  2. computing the number of combinations
    By clover in forum C Programming
    Replies: 34
    Last Post: 06-06-2004, 01:12 PM
  3. Grabbing Ctrl and Alt key combinations
    By scorpio_IITR in forum Linux Programming
    Replies: 0
    Last Post: 04-12-2004, 03:01 AM
  4. Combinations with factorial
    By fero45 in forum C++ Programming
    Replies: 4
    Last Post: 06-29-2002, 03:23 PM
  5. Combinations
    By GaPe in forum C Programming
    Replies: 16
    Last Post: 01-09-2002, 05:38 AM