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.

:
: 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?!?

:
: 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).

: 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).


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:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <windows.h>

// CLASS CRandom
//

#define Rand(start,end)        start + rand() % (end - start + 1)

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

    void            Init (unsigned int nLen, int nStart, int nEnd);
    void            Print ();
    void            Get ();
};

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


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

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

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

Here's how you would use it:

int main ()
{
    CRandom a(6, 1, 49);

    srand ((unsigned int)time(NULL));

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

    getch ();
}

---
edx - Member of CodeForce (http://codeforce.d2g.com)

Thanks for the class, I've used it, and played with it, but I have a couple of questions.

In this member function:

: void CRandom::Get ()
: {
: for (unsigned int i = 0; i < nnLen; i++)
: n[i] = nRandEnd + 1;
:
: for (unsigned int i = 0; i < nnLen; i++)
: {
: for (unsigned int v = 0; v < nnLen || n[i] == nRandEnd + 1; v++)
: {
: int 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?

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


True.


: 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).


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

---
edx - Member of CodeForce (http://codeforce.d2g.com)

: 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):

  #include <algorithm>
  #include <cassert>
  #include <iostream>
  #include <list>
  #include <map>
  using namespace std;

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

  int main() {
    // get fifteen random numbers in range [0-49]
    list<int> nums = unique_rand (15, 50);
    copy (nums.begin(), nums.end(), ostream_iterator<int>(cout, "\n"));
    return 0;
  }

You can easily modify it to return the list of numbers some other way that returning list<int> (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):

Perl

    sub unique_rand {
      my ($n, $max) = @_;
      my (@nums, %cache);
      while (@nums < $n) {
        my $rnd = int rand $max--;
        push @nums, $cache{$rnd} || $rnd;
        $cache{$rnd} = $cache{$max} || $max;
      }
      return @nums;
    }

Lua

  function unique_rand (n, max)
    assert(n <= max)
    local nums, cache = {}, {}
    for i=1,n do
      local rnd = floor(random() * max)
      max = max - 1
      tinsert(nums, cache[rnd] or rnd)
      cache[rnd]  = cache[max] or max
    end
    return nums
  end

Java

  List unique_rand (int n, int m) {
    List nums  = new LinkedList();
    Map  cache = new HashMap();
    while (n-- > 0) {
      Integer rnd = new Integer ((int) (Math.random() * m));
      Integer max = new Integer(--m);
      nums.add (      cache.get(rnd) != null ? cache.get(rnd) : rnd);
      cache.put (rnd, cache.get(max) != null ? cache.get(max) : max);
    }
    return nums;
  }

: 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<int> (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...

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

-- returns n unique random numbers from range min to max
function unique_rand (n, min, max)
  local res, buf = {}, {}
  local range = max - min + 1
  assert (n <= range)
  for i=1,n do
    local r = random(range) - 1
    range = range - 1
    res[i] = (buf[r] or r) + min
    buf[r] = buf[range] or range
  end
  return res
end

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:

  var = {}

Creates a Lua table, which is essenstially a hash-table (aka associative array).

  a, b, c = 1, 2, 3

Is the exact equivalent of:

  a = 1
  b = 2
  c = 3

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 :

<script language="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 : qiksearch@rediffmail.com

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<pickArr.length; i++)
{
if(numArr[currNum]==pickArr[i])
{
doFlag=true;
break;
}
}
}
if(!doFlag)
{
pickArr[count]=numArr[currNum];
document.write('<b>' + numArr[currNum] + '</b> <font color="#808080">|</font> ');
count+=1;
}
if(iterations<(numArr.length*3)) // Compare for max iterations you want
{
if((count<nums))
{
pickNums(nums);
}
}
else
{
location.reload();
}
}

pickNums(5); // Call the function, the argument is the number of elements you want to pick.
// Here we pick 5 unique random numbers
</script>

: 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

: : 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
:

Actually, it could matter, certain algorithms are faster.
I used one in my c++ class a couple years ago. (I've since upgraded to assembler, so I don't remember c++ syntax very well...) It works by making an array of booleans with as many elements as random numbers to be generated. Then, it checks each new number's element in the array, and if it's false, it makes it true and uses that number. If it's true already, it regenerates that number and tries again, until it succeeds.

I have coded this algorithm before in a lotto simulation program.
Essentially you must establish an array with 1 to maximum number of elements required (ie 1 to 49 in your example) Use RND to select a random number between 1..49. The trick now is to remove that number from the array so it cannot possibly be selected again. example : if the first random number picked was say 17, go to the array and starting at 17 - make it 18, so now the array reads 14, 15, 16, 18, 19, 20 etc do this by increasing each following number by one. When you next run the routine to pick a random nuber, change the upper value to (uppervalue - 1). you will see that the random number picked is merely a pointer to the nth position in the array. This is a confusing concept. Remember that the random number generated is not (necessarily) the number used, it merely identifies a position in the array. All positions in the array hold unique numbers. The array does not actually shrink at run time, the upper value is reduced by one each time a number is taken out. This simulates tha "taking out" of an element from the array. Hope you get my drift. It works great !
Good luck
Peter

Here's the code in JavaScript :

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Unique Random Numbers</title>
<!--BEGIN HEAD SECTION CODE-->
<script language="JavaScript">
// Unique Random Numbers
// -Picks a number of unique random numbers from an array
// By Premshree Pillai
// http://www.qiksearch.com
// http://premshree.resource-locator.com

function pickNums(nums, numArr)
{
if(nums>numArr.length)
return false;
var pickArr=new Array();
var tempArr=numArr;
for(var i=0; i<nums; i++)
{
pickArr[pickArr.length]=tempArr[Math.round((tempArr.length-1)*Math.random())];
var temp=pickArr[pickArr.length-1];
for(var j=0; j<tempArr.length; j++)
{
if(tempArr[j]==temp)
{
tempArr[j]=null;
var tempArr2=new Array();
for(var k=0; k<tempArr.length; k++)
if(tempArr[k]!=null)
tempArr2[tempArr2.length]=tempArr[k];
tempArr=tempArr2;
break;
}
}
}
return pickArr;
}
</script>
</head>
<!--END HEAD SECTION CODE-->
<body bgcolor="#FFFFFF">

<!--BEGIN BODY SECTION CODE-->
<script language="JavaScript">
/* Add Image Paths to this array */
var myArr = new Array("1","2","3","4","5","6","7","8");
var outArr=pickNums(5, myArr);

/* Print Output */
/* Modify this part to suit your output needs */
for(var i=0; i<outArr.length; i++)
{
document.write(outArr[i]);
}
</script>
<!--END BODY SECTION CODE-->

</body>
</html>