Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

picking six unique random numbers

TCaptainTCaptain Posts: 20Member
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

  • jeffpostjeffpost Posts: 316Member
    :
    : 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.

  • TCaptainTCaptain Posts: 20Member

    : 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?
  • jeffpostjeffpost Posts: 316Member
    :
    : 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-)

  • alan_pollockalan_pollock Posts: 110Member
    : :
    : : 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?!?
  • FelixFelix Posts: 438Member
    [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)

  • TCaptainTCaptain Posts: 20Member

    :
    : 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).
  • TCaptainTCaptain Posts: 20Member
    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?




  • Eric TetzEric Tetz Posts: 2,141Member
    : 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]

  • TCaptainTCaptain Posts: 20Member
    : 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...


  • FelixFelix Posts: 438Member
    [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)

«1
Sign In or Register to comment.