Thread: Lotto 6/49 program

  1. #46
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by wolly
    Ok,but how is that suppose to help me if I want to pick 6 numbers and not 49?
    The idea is that if you have a list of 49 numbers, to select the first 6 numbers at random without replacement, you do a partial shuffle such that the first 6 numbers out of the 49 are done with the shuffling (or you can completely shuffle all 49, that's fine too, just extra work). Then, you just need to select these first 6 numbers, ignoring the remaining 43, and you're done. Doing this right is slightly tricky though: Salem's post #44 demonstrates a somewhat different shuffling approach that arguably does too much and yet risks doing too little: you need to shuffle the entire list, and yet if you don't have enough iterations, you won't be shuffling enough.

    A correct and efficient approach is as given in the Knuth/Fisher-Yates shuffle: you repeatedly randomly select an item from the "unshuffled" portion of the list and swap it into position; the item that was swapped out of position now forms part of the "unshuffled" portion of the list, whereas the item that was swapped into position joins the "shuffled" portion of the list. This is basically akin to having a bag of items and taking them one by one at random to join your sequential hand of items. Therefore, you can do a partial shuffle with just 6 iterations with one swap each and you're done, needing only 6 random numbers to be generated.

    You might find it easier to implement another approach: build your list of random numbers by generating random numbers in the range and checking to see if it already exists if your list of generated numbers. If it doesn't, you add it to the list, otherwise you regenerate the random number. This approach works fine here because the number of numbers you want is much smaller than the range.
    Last edited by laserlight; 02-23-2020 at 05:16 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #47
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    Quote Originally Posted by laserlight View Post
    The idea is that if you have a list of 49 numbers, to select the first 6 numbers at random without replacement, you do a partial shuffle such that the first 6 numbers out of the 49 are done with the shuffling ....

    A correct and efficient approach is as given in the Knuth/Fisher-Yates shuffle: ...
    Incidentally, I mentioned using the Fisher-Yates algorithm in #4 and gave some code in #10 that does basically what you suggested. It seems like wolly either isn't reading or isn't understanding our replies.

  3. #48
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Quote Originally Posted by wolly View Post
    Ok,but how is that suppose to help me if I want to pick 6 numbers and not 49?
    Did it cross your mind that when you saw the output of
    Code:
      for(i=0;i<49;i++){
        printf("%d,",lotto[i]);
      }
    That changing it to
    Code:
      for(i=0;i<6;i++){
        printf("%d,",lotto[i]);
      }
    would just give you the 6 random numbers from the pool of 49 numbers.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #49
    Registered User
    Join Date
    Dec 2019
    Posts
    17
    Thank you for all your help but I expected a program like this:
    nk — ImgBB
    This example shows that if you input 6 numbers the program shows you the chances in percentage of winning or losing.
    Except the matching 6 numbers from 1 number which is useless.
    Last edited by wolly; 02-26-2020 at 11:38 AM.

  5. #50
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Right, so
    Code:
    int guess[6];
    for ( i = 0 ; i < 6 ; i++ ) {
        printf("Enter a number ");
        scanf("%d",&guess[i]);
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #51
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    277
    Just wanted to point out another simple approach to the whole random-shuffle thing. Use qsort() with some kind of randomizing callback. Crude example:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int randomize(const void* ignore, const void* unused)
    {
     return rand() % 2 ? 1 : -1;
    }
    
    int main(void)
    {
     srand(time(NULL));
     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
     const int length = sizeof(array) / sizeof(int);
     qsort(array, length, sizeof(int), randomize);
     for(int index = 0; index < length; ++index)
      printf("%d\n", array[index]);  
    }

  7. #52
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Sir Galahad
    Use qsort() with some kind of randomizing callback.
    That's probably not a good idea though as it technically goes against the C standard requirements for qsort:
    When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key.
    and then there's the thing whereby a general purpose comparison-sort algorithm as would be used to implement qsort takes O(n log n) in the average case (and possibly worst case, but not always), whereas a Knuth/Fisher-Yates shuffle takes linear time even in the worst case, and faster yet (for the constant factor) with a partial shuffle.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #53
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    277
    Quote Originally Posted by laserlight View Post
    That's probably not a good idea though as it technically goes against the C standard requirements for qsort:

    and then there's the thing whereby a general purpose comparison-sort algorithm as would be used to implement qsort takes O(n log n) in the average case (and possibly worst case, but not always), whereas a Knuth/Fisher-Yates shuffle takes linear time even in the worst case, and faster yet (for the constant factor) with a partial shuffle.
    I see! After some testing it does indeed seem to lead to something like N*log(N) comparisons. I don't think I've ever heard of the Knuth-Fisher-Yates shuffle. Such an elegant and efficient approach, yet so simple...
    Last edited by Sir Galahad; 03-05-2020 at 05:45 AM.

  9. #54

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. lotto program homework help
    By apelletier in forum C Programming
    Replies: 14
    Last Post: 03-11-2018, 02:09 PM
  2. Lotto program
    By MrQ in forum C Programming
    Replies: 3
    Last Post: 06-24-2013, 12:35 AM
  3. lotto program in c
    By vyshant in forum C Programming
    Replies: 7
    Last Post: 11-07-2011, 12:19 PM
  4. Lotto problem
    By Roaring_Tiger in forum C Programming
    Replies: 11
    Last Post: 03-13-2003, 10:17 PM
  5. Lotto game in C
    By fun2sas in forum C Programming
    Replies: 2
    Last Post: 03-02-2003, 07:19 PM

Tags for this Thread