Generating Random # in Array without repeats

exiledpaladin05 · #1 01-Mar-2009, 20:19

hey guys I'm having a problem generating a random number in an array without any repeats. I believe the problem is within my inner for loop but I'm not sure exactly what it is.

CPP / C++ / C Code:

	for (int i=0;i<5;i++)
	{
        // generate a random number
        rgiComp_Numbers[i]= rand()%5;

        for (int j=0; j<5;j++)
        {
        if (rgiComp_Numbers[i]==rgiComp_Numbers[j])
       
           rgiComp_Numbers[i]= rand()%5;
        }

        cout <<rgiComp_Numbers[i]<<" ";
	}

i think the problem is that the inner loop re randoms the number the first time then increments... im not sure how to fix this... if anyone could help would be very appreciated... thanks.

ocicat · #2 01-Mar-2009, 23:21

Quote:

Originally Posted by exiledpaladin05

hI believe the problem is within my inner for loop but I'm not sure exactly what it is.

You haven't articulated what should be happening nor what is happening. Although this may seem to be a minor point, if you do not understand what is the end goal, there is little way of determining whether you have arrived at a viable solution, nor how to get there.

Having said that, it appears that you have an array of five elements of which you want to randomly assign the values 0-4. The point of the inner loop is to ensure that whatever random number is chosen, it has not been previously assigned to an earlier element. You have the beginnings of implementing this algorithm, & you are correct that it is not complete, so the next step is to devise a strategy to arrive at a workable solution.

With pencil & paper, how would you determine whether any random number has previously been assigned? There are two choices:

The simple case is that the new random number generated has not been used before. In this case, assign it to the current element, & move to the next iteration.

The other alternative is that the value has previously been assigned. Here, you have choose another random value, & determine if it has been assigned. The obvious choice in this situation is to use a while-loop in conjunction with the inner nested loop, & here is the beginning of what you need to consider in pseudocode:

Code:

get a new random value
set a flag which represents whether a random value has been assigned
while a value has not been assigned
    iterate through the array to determine whether this random value has already been used.
    If the random value has been used
        generate another random value, & check each element of the array again
    else
        set the flag such that the while-loop is exited.
    end while-loop

Think about this, & experiment with the code. If you are still having problems, post what code you have completed so discussion can continue.

exiledpaladin05 · #3 02-Mar-2009, 17:06

I understand that:

i set a random value to a[0]
so a[0] = 1;
then i check a[0] with a[1];
if a[0] == a[1]
random a new number until a[0] != a[1]
then move onto a[1]
check a[1] with a[0]
if a[1] == a[0]
random a new number until a[1] != a[0]

i guess the part that I'm not getting is the code on how to check the previous value without checking the value of the current value...

such has I check a[1] with a[0]... then i check a[1] with a[1]... how do i avoid checking a[1] with a[1]

this is the unsuccessful code I've come up with again.

CPP / C++ / C Code:

        for (int i=0;i<5;i++)
	    {
            rgiComp_Numbers[i]= rand()%5;
             for (int i=0; i<5;i++)
            {
            while(rgiComp_Numbers[i]==rgiComp_Numbers[i-1])
            {
                rgiComp_Numbers[i]= rand()%5;
            }

             }

            cout <<rgiComp_Numbers[i]<<" ";
        }

davekw7x · #4 02-Mar-2009, 18:54

Quote:

Originally Posted by exiledpaladin05

.
i guess the part that I'm not getting is the code on how to check the previous value without checking the value of the current value...

You need a loop with another variable. For each value of i, this new variable starts at zero and goes up through the previously assigned values. If it gets all of the way up through i-1 without finding that the current random value has already been assigned, then you can use the current random value, otherwise you have to try again.

I think you could try something like the following semi-pseudo code. See Footnote.

Given an array with num elements:

We want to assign values 0, 1, ..., num-1 "randomly" to the members of the array, with no repeated values.

Here is a naive method ("brute force"):

Code:

   LOOP1: for (i = 0; i < num; i++)
     SET x[i] = -1  // This can not be a legal value. It gets us started in LOOP2
     LOOP2: WHILE (x[0] < 0)       // Will loop until we do get a legal value for x[i]
       SET x[i] equal to rand()%num.  //This is the candidate for this i
       LOOP3: for (j = 0; j < i; j++) // Look at all previous elements
         IF (x[i] == x[j]) THEN         // can't use this one
           SET x[i] = -1                // This makes the "while" loop continue
           BREAK                        // out of the innermost "if" loop
         END IF
       END LOOP3
       // At this point, if x[i] is not a negative number, we
       // are finished with this i; if x[i] is negative, we
       // have to try another candidate
     END LOOP2
     //
     //The only way it gets out of LOOP2 is if it didn't find 
     //any previous values equal to this candidate, so x[i] is OK
     //
  END LOOP1 // We leave this loop when all x[i] have been assigned

I think that this is what you are trying to get at. Look at LOOP3: It investigates only the values of array members that have already been assigned.

There are other ways of doing the deed that have considerable advantages, especially for large data sets. Specifically: Initialize the array sequentially, then perform a random shuffle. (Look it up if you are interested. The code is actually simpler than this, but I think it's important to understand how to do it the way that you started.)

Regards,

Dave

Footnote: I call it semi-pseudo code because, unlike true pseudo code, it has some language-specific constructs.

Every time someone talks about pseudo code, I get a flashback to:

"I may be pseudo-intellectual, but at least I'm not quasi."
---William F. Buckley
Responding to some non-constructive criticism about his conservative views way back in the mid-20th century.

exiledpaladin05 · #5 10-Mar-2009, 00:55

I've tried the above code and I'm still getting duplicate numbers...

CPP / C++ / C Code:

for (int i=0; i<ARRAY_SIZE; i++)
{
    rgiComp_Numbers[i]=-1;
   
    while(rgiComp_Numbers[i]<0)
    {
        rgiComp_Numbers[i]= rand()%10;
        
        cout<< rgiComp_Numbers[i]<<endl;

        for(int j=0; j<i; j++)
        {
            if (rgiComp_Numbers[i]==rgiComp_Numbers[j])
            {
                rgiComp_Numbers[i]=-1;
                break;
            }
        }
        if (rgiComp_Numbers[i]<0)
        {
            rgiComp_Numbers[i]= rand()%10;
        }
    }
}

am i sitll missing part of the code?

Peter_APIIT · #6 10-Mar-2009, 04:38

std::unique() may help.

I will random each number in an array and check using unique.

For example, 0, 1, 2, 3, 4 -- 5;
loop == 1 then i check with unique
loop == 2 then i check with unique if not unique rerand() with another seed value;

or if you don't want to use unique(), then you have check one by one from start of array until the element being rand().
Hope helps.

davekw7x · #7 10-Mar-2009, 08:32

Quote:

Originally Posted by exiledpaladin05

I've tried the above code and I'm still getting duplicate numbers...

CPP / C++ / C Code:

for (int i=0; i<ARRAY_SIZE; i++)
{
    rgiComp_Numbers[i]=-1;
   
    while(rgiComp_Numbers[i]<0)
    {
        rgiComp_Numbers[i]= rand()%10;
        
        cout<< rgiComp_Numbers[i]<<endl;

        for(int j=0; j<i; j++)
        {
            if (rgiComp_Numbers[i]==rgiComp_Numbers[j])
            {
                rgiComp_Numbers[i]=-1;
                break;
            }
        }
//
// If you detected a duplicate, the following generates a random value that
// is not less than zero, so the while(...) loop will not continue. Period.
//
// The value generated here may very well be a duplicate.
//
// Why did you put this here?
//
        if (rgiComp_Numbers[i]<0)
        {
            rgiComp_Numbers[i]= rand()%10;
        }
    }
}

am i sitll missing part of the code?

1. You didn't implement my pseudo code, and I put comments in to show what's wrong.

2. Instrument your code to make it tell you exactly what it is printing. Before changing anything else, change your print statement to be more verbose. Put in another print statement in the block that I objected to in my comments. Maybe something like

CPP / C++ / C Code:

    for (int i=0; i<ARRAY_SIZE; i++)
    {
        rgiComp_Numbers[i] = -1;
        while(rgiComp_Numbers[i] < 0)
        {
            rgiComp_Numbers[i]= rand()%10;
            cout<< "1: rgiComp_Numbers[" << i << "] = " 
                 << rgiComp_Numbers[i]<<endl;

            for(int j=0; j<i; j++)
            {
                if (rgiComp_Numbers[i]==rgiComp_Numbers[j])
                {
                    rgiComp_Numbers[i]=-1;
                    break;
                }
            }
            if (rgiComp_Numbers[i]<0)
            {
                rgiComp_Numbers[i]= rand()%10;
                cout<< "2: rgiComp_Numbers[" << i << "] = " 
                    << rgiComp_Numbers[i]<<endl;
            }
        }
    }
    for (int i = 0; i < ARRAY_SIZE; i++) {
        cout << "rgiComp_Numbers[" << i << "] = " 
             << rgiComp_Numbers[i] << endl;
    }

3. What is the value of ARRAY_SIZE? If it is greater than 10, the corrected code will loop infinitely, since your code can generate at most ten different numbers. 0, 1, 2, 3, 4, 5, 6, 7, 8. 9.

4. You are printing out all values that you get from rand(), including duplicates. Try ARRAY_SIZE = 10 (or smaller), and print out that many array values after you leave the the "while(..." loop.

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
where is the problem and can you fix it (php)	oggie	MySQL / PHP Forum	8	14-Apr-2008 16:08
Getting a line error in register	oggie	MySQL / PHP Forum	5	13-Apr-2008 17:16
Returning a 2 dimensional Array from a function	vicky_brsh	C++ Forum	1	04-Jan-2008 15:06
Need help deleting the last element in the array	headphone69	C++ Forum	2	15-Mar-2006 20:31
generating arrays from main multi-dimensional array	raisinlove	MySQL / PHP Forum	1	25-Jul-2005 13:29

Generating Random # in Array without repeats

Re: Generating Random # in Array without repeats

Re: Generating Random # in Array without repeats

Re: Generating Random # in Array without repeats

Re: Generating Random # in Array without repeats

Re: Generating Random # in Array without repeats

Re: Generating Random # in Array without repeats