picking six unique random numbers

I'm toying around with a program in C++ that picks a user defined amount of number sets (ie: 6 numbers per set, and the user may want 100 sets) and then gives me a count of how many times each number was picked (right now its 1 to 49).

My problem is that when I am picking a set of 6 numbers I am wracking my brains to find a way to make it pick only 6 unique numbers...

Right now I have 2 loops and somehow it doesn't seem to be elegant.

do loop until 6 numbers are actually picked
- get a random number (I'm using RAND right now)
- start another loop (6 times)
- check latest pick against the numbers picked before
(stored in a temporary array)
- end loop, if number wasn't found, then add to set and
increment the numbers that were picked
end loop

I'm just curious if someone might have a nicer way to do it, I can post code if needed, but I'm interested in the algorithm since I keep playing with this thing as a way to practice coding C++ (I learned to program in C and C++ but been working COBOL and mainframes for the last 5 years so I never did anything with it beyond the basics I was taught in college and I want to change that).

Thanks in advance for your help, I've been reading the boards for weeks but its my first question...this place totally rocks.
«1

Comments

  • :
    : do loop until 6 numbers are actually picked
    : - get a random number (I'm using RAND right now)
    : - start another loop (6 times)
    : - check latest pick against the numbers picked before
    : (stored in a temporary array)
    : - end loop, if number wasn't found, then add to set and
    : increment the numbers that were picked
    : end loop
    :
    :
    Looks ok to me. BTW, there's no such thing as a random number, only random sequences.


  • : Looks ok to me. BTW, there's no such thing as a random number, only random sequences.
    :
    :

    Well ok then, random sequences if you want to get picky :)

    I'm still toying with it, and I'm happy to get a second opinion that says my solution looks ok (thank you for your reply) but you know...ever get that feeling when you look at a piece of code that it could be done better, but you can't figure out how?
  • :
    : I'm still toying with it, and I'm happy to get a second opinion that says my solution looks ok (thank you for your reply) but you know...ever get that feeling when you look at a piece of code that it could be done better, but you can't figure out how?
    :

    Frequently. 8-)

  • : :
    : : I'm still toying with it, and I'm happy to get a second opinion that says my solution looks ok (thank you for your reply) but you know...ever get that feeling when you look at a piece of code that it could be done better, but you can't figure out how?
    : :
    :
    : Frequently. 8-)
    :
    :


    LOL... are these by any chance for lottery picks?!?
  • [italic]
    : I'm just curious if someone might have a nicer way to do it, I can post code if needed, but I'm interested in the algorithm since I keep playing with this thing as a way to practice coding C++ (I learned to program in C and C++ but been working COBOL and mainframes for the last 5 years so I never did anything with it beyond the basics I was taught in college and I want to change that).
    [/italic]

    A similar question was asked on another messageboard a few days ago:

    http://www.programmersheaven.com/community/MsgBoard/read.asp?Board=69&MsgID=102761&Setting=A9998F0301

    I wrote a class which handles those problems. I don't know weather it is really fast, but it seems to work:

    [code]
    [blue]#include[/blue]
    [blue]#include[/blue]
    [blue]#include[/blue]
    [blue]#include[/blue]
    [blue]#include[/blue]

    [green]// CLASS CRandom[/green]
    [green]//[/green]

    [blue]#define[/blue] Rand(start,end) start + rand() % (end - start + 1)

    [blue]class[/blue] CRandom
    {
    [blue]private[/blue]:
    [blue]int[/blue] *n,
    nRandStart,
    nRandEnd;
    [blue][blue]unsigned[/blue][/blue] [blue]int[/blue] nnLen;
    [blue]public[/blue]:
    CRandom () { Init (6, 1, 53); }
    CRandom ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] nLen, [blue]int[/blue] nStart, [blue]int[/blue] nEnd) { Init (nLen, nStart, nEnd); }
    ~CRandom () { [blue]delete[/blue] [] n; }

    [blue]void[/blue] Init ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] nLen, [blue]int[/blue] nStart, [blue]int[/blue] nEnd);
    [blue]void[/blue] Print ();
    [blue]void[/blue] Get ();
    };

    [green]// Init[/green]
    [green]// initialize class (allocate space..)[/green]
    [blue]void[/blue] CRandom::Init (
    [blue][blue]unsigned[/blue][/blue] [blue]int[/blue] nLen, [green]// how many numbers to generate[/green]
    [blue]int[/blue] nStart, [green]// first possible number[/green]
    [blue]int[/blue] nEnd [green]// last possible number[/green]
    )
    {
    nnLen = nLen;
    nRandStart = nStart;
    nRandEnd = nEnd;
    n = [blue]new[/blue] [blue]int[/blue] [nLen];
    }


    [green]// Get[/green]
    [green]// get (no double) random numbers[/green]
    [blue]void[/blue] CRandom::Get ()
    {
    [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] i = 0; i < nnLen; i++)
    n[i] = nRandEnd + 1;

    [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] i = 0; i < nnLen; i++)
    {
    [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] v = 0; v < nnLen || n[i] == nRandEnd + 1; v++)
    {
    [blue]int[/blue] j = Rand (nRandStart, nRandEnd - nnLen + i + 1);
    n[i] = (j < n[i] && j > ((i == 0)?0:n[i - 1]))?j:n[i];
    }
    }
    }

    [green]// Print[/green]
    [green]// print out generated numbers[/green]
    [blue]void[/blue] CRandom::Print ()
    {
    [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] i = 0; i < nnLen; i++)
    printf ("%d ", n[i]);
    printf ("
    ");
    }
    [/code]

    Here's how you would use it:

    [code]
    [blue]int[/blue] main ()
    {
    CRandom a(6, 1, 49);

    srand (([blue][blue]unsigned[/blue][/blue] [blue]int[/blue])time(NULL));

    [blue]for[/blue] ([blue]int[/blue] i = 0; i < 10; i++)
    {
    a.Get ();
    a.Print ();
    }

    getch ();
    }
    [/code]

    ---
    [b]edx[/b] - Member of [blue][b]CodeForce[/b][/blue] (http://codeforce.d2g.com)


  • :
    : LOL... are these by any chance for lottery picks?!?
    :

    Well yeah, that's how it started. I mean it means nothing to me that they are 6/49 lottery picks. It started as an argument between me and a friend over coding practice.. For some reason he described to me this program that he wanted to play with and couldn't get his mind around storing the total times each number (from 1 to 49) had been picked into an arrray of 49 ints. So I coded the barebones of it to show him and then I started toying with it more and more. It was just the thing to get my kickstart back into C++ coding (currently I work with mainframes and its boring as h*ll).
  • Thanks for the class, I've used it, and played with it, but I have a couple of questions.

    In this member function:

    : [blue]void[/blue] CRandom::Get ()
    : {
    : [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] i = 0; i < nnLen; i++)
    : n[i] = nRandEnd + 1;
    :
    : [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] i = 0; i < nnLen; i++)
    : {
    : [blue]for[/blue] ([blue][blue]unsigned[/blue][/blue] [blue]int[/blue] v = 0; v < nnLen || n[i] == nRandEnd + 1; v++)
    : {
    : [blue]int[/blue] j = Rand (nRandStart, nRandEnd - nnLen + i + 1);
    : n[i] = (j < n[i] && j > ((i == 0)?0:n[i - 1]))?j:n[i];
    : }
    : }
    : }
    :

    I notice that the condition (I think) basically works in that you pick the first random number...then you keep making sure each pick is higher than the last...which means there are no duplicates.

    However, when i=0, what happens if Rand() returns the highest number possible?

    I tried this and the program just gets stuck. (I forced in 49, I haven't played with it in debug yet).

    Its cool code otherwise though...any ideas?




  • : My problem is that when I am picking a set of 6 numbers I am wracking my brains to find a way to make it pick only 6 unique numbers...

    Here's an algorithm that will give you n unique random numbers on O(n) time (i.e. - one pass):
    [code=ffffff]
    [color=a020f0]#include [/color][color=bb0000][/color]
    [color=a020f0]#include [/color][color=bb0000][/color]
    [color=a020f0]#include [/color][color=bb0000][/color]
    [color=a020f0]#include [/color][color=bb0000][/color]
    [color=a020f0]#include [/color][color=bb0000]
    [/color]
    [color=000000][b]using[/b][/color] [color=000080]namespace[/color] std;

    list<[color=000080]int[/color]> unique_rand ([color=000080]int[/color] n, [color=000080]int[/color] max) {
    assert (n <= max); [color=80a0b0][italic]// this is an obvious requirement ;)[/italic][/color]
    list<[color=000080]int[/color]> nums;
    map<[color=000080]int[/color], [color=000080]int[/color]> cache;
    [color=000000][b]while[/b][/color] (n--) {
    [color=000080]int[/color] rnd = rand() % max--;
    nums.push_back ((cache.find(rnd) != cache.end()) ? cache[rnd] : rnd);
    cache[rnd] = (cache.find(max) != cache.end()) ? cache[max] : max;
    }
    [color=000000][b]return[/b][/color] nums;
    }

    [color=000080]int[/color] main() {
    [color=80a0b0][italic]// get fifteen random numbers in range [0-49][/italic][/color]
    list<[color=000080]int[/color]> nums = unique_rand ([color=bb0000]15[/color], [color=bb0000]50[/color]);
    copy (nums.begin(), nums.end(), ostream_iterator<[color=000080]int[/color]>(cout, [color=bb0000]"[/color][color=907050]
    [/color][color=bb0000]"[/color]));
    [color=000000][b]return[/b][/color] [color=bb0000]0[/color];
    }
    [/code]
    You can easily modify it to return the list of numbers some other way that returning list (such as passing in an appropriately sized int array). You could also modify it to select random numbers in a range (min-max) rather than the current (0-max). I'll leave that as an exercise for you. ;)

    Cheers,
    Eric

    P.S. Here's the same algorithm in Perl, Lua and Java (because I'm bored):

    [b]Perl[/b]
    [code=ffffff]
    [color=804040][b] [/b][/color][color=000000][b]sub[/b][/color][color=804040][b] [/b][/color][color=804040][b]unique_rand[/b][/color][color=804040][b] [/b][/color]{
    [color=000000][b]my[/b][/color] ([color=804040][b]$n[/b][/color], [color=804040][b]$max[/b][/color]) = [color=804040][b]@_[/b][/color];
    [color=000000][b]my[/b][/color] ([color=804040][b]@nums[/b][/color], [color=804040][b]%cache[/b][/color]);
    [color=000000][b]while[/b][/color] ([color=804040][b]@nums[/b][/color] < [color=804040][b]$n[/b][/color]) {
    [color=000000][b]my[/b][/color] [color=804040][b]$rnd[/b][/color] = [color=000000][b]int[/b][/color] [color=000000][b]rand[/b][/color] [color=804040][b]$max[/b][/color]--;
    [color=000000][b]push[/b][/color] [color=804040][b]@nums[/b][/color], [color=804040][b]$cache[/b][/color]{[color=804040][b]$rnd[/b][/color]} || [color=804040][b]$rnd[/b][/color];
    [color=804040][b]$cache[/b][/color]{[color=804040][b]$rnd[/b][/color]} = [color=804040][b]$cache[/b][/color]{[color=804040][b]$max[/b][/color]} || [color=804040][b]$max[/b][/color];
    }
    [color=000000][b]return[/b][/color] [color=804040][b]@nums[/b][/color];
    }
    [/code]
    [b]Lua[/b]
    [code=ffffff]
    [color=804040][b]function[/b][/color] unique_rand (n, max)
    assert(n <= max)
    [color=000000][b]local[/b][/color] nums, cache = [color=000080]{}[/color], [color=000080]{}[/color]
    [color=000000][b]for[/b][/color] i=[color=bb0000]1[/color],n [color=000000][b]do[/b][/color]
    [color=000000][b]local[/b][/color] rnd = floor(random() * max)
    max = max - [color=bb0000]1[/color]
    tinsert(nums, cache[rnd] [color=000000][b]or[/b][/color] rnd)
    cache[rnd] = cache[max] [color=000000][b]or[/b][/color] max
    [color=000000][b]end[/b][/color]
    [b]return[/b] nums
    [color=804040][b]end[/b][/color]
    [/code]
    [b]Java[/b]
    [code=ffffff]
    List unique_rand ([color=000080]int[/color] n, [color=000080]int[/color] m) {
    List nums = [color=000000][b]new[/b][/color] LinkedList();
    Map cache = [color=000000][b]new[/b][/color] HashMap();
    [color=000000][b]while[/b][/color] (n-- > [color=bb0000]0[/color]) {
    Integer rnd = [color=000000][b]new[/b][/color] Integer (([color=000080]int[/color]) (Math.random() * m));
    Integer max = [color=000000][b]new[/b][/color] Integer(--m);
    nums.add ( cache.get(rnd) != null ? cache.get(rnd) : rnd);
    cache.put (rnd, cache.get(max) != null ? cache.get(max) : max);
    }
    [color=000000][b]return[/b][/color] nums;
    }
    [/code]

  • : Here's an algorithm that will give you n unique random numbers on O
    :(n) time (i.e. - one pass):

    Thanks! More code to play with :)

    : You can easily modify it to return the list of numbers some other way
    :that returning list (such as passing in an appropriately sized
    :int array). You could also modify it to select random numbers in a
    :range (min-max) rather than the current (0-max). I'll leave that as
    :an exercise for you. ;)


    I very much appreciate it actually :) This whole thing sounds pretty dinky, but it got me back into C++ programming and MFC app development so I'm having a lot of fun tinkering.


    :
    : P.S. Here's the same algorithm in Perl, Lua and Java (because I'm
    :bored)

    Also a big thank you there, I've been toying with Perl for a while, although I have NO clue what LUA is...


  • [italic]
    : I notice that the condition (I think) basically works in that you pick the first random number...then you keep making sure each pick is higher than the last...which means there are no duplicates.
    [/italic]

    True.

    [italic]
    : However, when i=0, what happens if Rand() returns the highest number possible?
    :
    : I tried this and the program just gets stuck. (I forced in 49, I haven't played with it in debug yet).
    [/italic]

    Also true. I wrote this from scratch and didn't implement things like "error checking".

    ---
    [b]edx[/b] - Member of [blue][b]CodeForce[/b][/blue] (http://codeforce.d2g.com)

  • : I have NO clue what LUA is...

    Lua rocks. It's a tiny, functional language (functions are first class object). It's easy to learn, easy to read, and is very powerful, but best of all: it is designed to be embedded in other applications. You can extend the language from C or C++ code and use it as scripting language for your app. It's tiny (will add about 50Kb to your app), and is super fast (faster than almost all other interpreted scripting languages, including Perl, Python, Tcl, etc.).

    http://www.lua.org

    Cheers,
    Eric
  • I updated the Lua version to allow a specific range of random numbers to be produced.
    [code=ffffff]
    [color=80a0b0][italic]-- returns n unique random numbers from range min to max[/italic][/color]
    [color=804040][b]function[/b][/color] unique_rand (n, min, max)
    [color=000000][b]local[/b][/color] res, buf = [color=000080]{}[/color], [color=000080]{}[/color]
    [color=000000][b]local[/b][/color] range = max - min + [color=bb0000]1[/color]
    assert (n <= range)
    [color=000000][b]for[/b][/color] i=[color=bb0000]1[/color],n [color=000000][b]do[/b][/color]
    [color=000000][b]local[/b][/color] r = random(range) - [color=bb0000]1[/color]
    range = range - [color=bb0000]1[/color]
    res[i] = (buf[r] [color=000000][b]or[/b][/color] r) + min
    buf[r] = buf[range] [color=000000][b]or[/b][/color] range
    [color=000000][b]end[/b][/color]
    [color=000000][b]return[/b][/color] res
    [color=804040][b]end[/b][/color]
    [/code]
    I updated the Lua version, because it is probably the closest to pseudocode. As a matter of fact, Lua would be a great language for describing algorithms on the Algorithm board. A couple notes about Lua for anyone reading this code:
    [code=ffffff]
    var = {}
    [/code]
    Creates a Lua table, which is essenstially a hash-table (aka associative array).
    [code=ffffff]
    a, b, c = [color=bb0000]1[/color], [color=bb0000]2[/color], [color=bb0000]3[/color]
    [/code]
    Is the exact equivalent of:
    [code=ffffff]
    a = [color=bb0000]1[/color]
    b = [color=bb0000]2[/color]
    c = [color=bb0000]3[/color]
    [/code]
    random() returns a floating point value from 0 to 1, so floor(random() * n) yields an integer from 0 to n-1.

    Cheers,
    Eric

  • Here's a related JavaScript :


    // Unique Random Numbers Picker
    // -Picks a number of unique random numbers from an array
    // (c) 2002 Premshree Pillai
    // http://www.qiksearch.com, http://javascript.qik.cjb.net
    // E-mail : [email protected]

    var numArr = new Array("0","1","2","3","4","5","6","7","8","9"); // Add elements here
    var pickArr = new Array(); // The array that will be formed
    var count=0;
    var doFlag=false;
    var iterations=0;

    function pickNums(nums)
    {
    iterations+=1;
    var currNum = Math.round((numArr.length-1)*Math.random());
    if(count!=0)
    {
    for(var i=0; i' + numArr[currNum] + ' | ');
    count+=1;
    }
    if(iterations
  • : I'm toying around with a program in C++ that picks a user defined amount of number sets (ie: 6 numbers per set, and the user may want 100 sets) and then gives me a count of how many times each number was picked (right now its 1 to 49).
    :
    : My problem is that when I am picking a set of 6 numbers I am wracking my brains to find a way to make it pick only 6 unique numbers...
    :
    : Right now I have 2 loops and somehow it doesn't seem to be elegant.
    :
    : do loop until 6 numbers are actually picked
    : - get a random number (I'm using RAND right now)
    : - start another loop (6 times)
    : - check latest pick against the numbers picked before
    : (stored in a temporary array)
    : - end loop, if number wasn't found, then add to set and
    : increment the numbers that were picked
    : end loop
    :
    : I'm just curious if someone might have a nicer way to do it, I can post code if needed, but I'm interested in the algorithm since I keep playing with this thing as a way to practice coding C++ (I learned to program in C and C++ but been working COBOL and mainframes for the last 5 years so I never did anything with it beyond the basics I was taught in college and I want to change that).
    :
    : Thanks in advance for your help, I've been reading the boards for weeks but its my first question...this place totally rocks.
    :


    here is my own algorithm in a pseudo-language(sorry) to pick 6 unique numbers in a set of numbers between 1 to 49 for an exemple.

    //init
    int tabNumbers[49];
    int tabResult[6]; // buffer for the sixs numbers.
    for (int i=0; i<49;i++) tabNumbers[i]=i+1;

    int last=48;

    // pick 6 numbers.
    for (i=0;i<6;i++)
    {
    int x=random number between 0 and last;
    result=tabNumbers[x];
    tabNumbers[x]=tabNumbers[last];
    tabNumbers[last]=result;
    last--;
    tabResult[i]=result;
    }


    and then, if you want to pick another set of six numbers, just do
    last=48; and redo the loop.

    fabulous , not ? ;)



  • : I'm toying around with a program in C++ that picks a user defined amount of number sets (ie: 6 numbers per set, and the user may want 100 sets) and then gives me a count of how many times each number was picked (right now its 1 to 49).
    :
    : My problem is that when I am picking a set of 6 numbers I am wracking my brains to find a way to make it pick only 6 unique numbers...
    :
    : Right now I have 2 loops and somehow it doesn't seem to be elegant.
    :
    : do loop until 6 numbers are actually picked
    : - get a random number (I'm using RAND right now)
    : - start another loop (6 times)
    : - check latest pick against the numbers picked before
    : (stored in a temporary array)
    : - end loop, if number wasn't found, then add to set and
    : increment the numbers that were picked
    : end loop
    :
    : I'm just curious if someone might have a nicer way to do it, I
    :can post code if needed, but I'm interested in the algorithm since I
    :keep playing with this thing as a way to practice coding C++ (I
    :learned to program in C and C++ but been working COBOL and mainframes
    :for the last 5 years so I never did anything with it beyond the basics
    :I was taught in college and I want to change that).
    :
    : Thanks in advance for your help, I've been reading the boards for
    :weeks but its my first question...this place totally rocks.
    :


    Hello!
    primarily, its totally no matter which algo you are using for your
    6 out of 49 lottery program, as long as it WORKS properly, without duplicates and "number holes" or
    repetitious series of numbers(in BASIC i would prevent this by the RANDOMIZE TIMER statement, and its ok)
    so just write YOUR code!

    But btw, could you tell me where to get a good C/C++ Interpreter/Compiler/Development environment from?
    I would like to start programming in C/C++/VisualC++ too, after BASIC,
    VisualBASIC and a little Pascal and ASM(with Microsofts DEBUG!! ;-) ).
    What Compiler/Environment are you using?

    Thank you in advance
    Mac
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories