3 Replies - 485 Views - Last Post: 18 February 2013 - 05:08 AM Rate Topic: -----

#1 CS2012  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 12
  • Joined: 04-February 13

generate a random number into an array without dups using rand()

Posted 17 February 2013 - 11:30 PM

Hi guys, I'm currently working on assignment which requires to generate a random permutation of the first N integers. For example, if N = 4, one possible answer is {3,1,2,4} without duplicates. {3,3,2,4} is not correct

To fill a[4], generate random numbers until you get one that is not already in a[0], a[1], ..., a[n-1]. for a[0] whatever random number you generate can be put in it. So here is my code. I don't think my check for duplicates is right because I debugged it and it only tested each position once and never checked again. Any suggestions would be appreciated

#include <iostream>
#include <stdlib.h> 
#include <time.h> 


using namespace std;
int main()
{
	/* initialize random seed */
	 srand (time(NULL));
	
	 int a[4];
    int num = 0; //variable to store the number in

//generate random numbers:
for (int i=0;i<4;i++)
{
	if(i==0)
	{
		num=rand()%4+1;
		a[i] = num;
	}
	else
	{
                 
		num = rand()%4+1;
		a[i] = num;
                //check for duplicates
		for (int j=0; j<i; j++)
		{
		     while (a[i] == a[j])
			{
				num=rand()%4+1;
				a[i]= num;
			}
				
		} 
	}
	
}
	for(int i=0; i<4; i++)
		cout<<a[i]<<" ";
	cout<<endl;

	system("PAUSE");
	return 0;
}




Is This A Good Question/Topic? 0
  • +

Replies To: generate a random number into an array without dups using rand()

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4189
  • View blog
  • Posts: 11,863
  • Joined: 18-April 07

Re: generate a random number into an array without dups using rand()

Posted 18 February 2013 - 12:01 AM

You don't want to be changing the value in a[i], those are your set values. You want to be generating a number (num) and then simply looping through a[] from 0 to i and if any of them match, randomize num again and start the loop over.

Here is something to chew on as your else statement...

else
{
    bool found = true;

    // Keep going while number is already found in array.
    while (found) {
        found = false;

        // Generate a fresh number
        num = rand()%4+1;

        // Loop through numbers 0 to i
        for (int j=0; j<i; j++)
        {
            // If prev number is equal to this num
            // found is true, break to while and need to regenerate again.
            if (a[j] == num)
            {
                found = true;
                break;
            }		
        } 
    }

    // Once we get out of while loop
    // num is not already in a[]
    a[i] = num;

}



:)
Was This Post Helpful? 0
  • +
  • -

#3 CS2012  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 12
  • Joined: 04-February 13

Re: generate a random number into an array without dups using rand()

Posted 18 February 2013 - 12:14 AM

View PostMartyr2, on 18 February 2013 - 12:01 AM, said:

You don't want to be changing the value in a[i], those are your set values. You want to be generating a number (num) and then simply looping through a[] from 0 to i and if any of them match, randomize num again and start the loop over.

Here is something to chew on as your else statement...

else
{
    bool found = true;

    // Keep going while number is already found in array.
    while (found) {
        found = false;

        // Generate a fresh number
        num = rand()%4+1;

        // Loop through numbers 0 to i
        for (int j=0; j<i; j++)
        {
            // If prev number is equal to this num
            // found is true, break to while and need to regenerate again.
            if (a[j] == num)
            {
                found = true;
                break;
            }		
        } 
    }

    // Once we get out of while loop
    // num is not already in a[]
    a[i] = num;

}



:)/>


I did find something similar to that but I don't wanna use someone else code because its not right. so I wonder if I can use for loop to check for duplicates and replace it with a random number. And Thanks for the reply I will look at the code :)
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: generate a random number into an array without dups using rand()

Posted 18 February 2013 - 05:08 AM

If the "random" numbers are always 1..N+1 in your array[N], then you don't have a random number generation problem.

Instead, what if you have, is a random order problem. Fill your array with the values is should have, then just "shuffle" it. You'll find many examples for decks of cards.

Version 1: common because it's simple. Pick two positions at random, swap the values. Do this for some time until you feel things are shuffled. This works, but because you'll end up going over the same ground a lot, it can take N*N swaps or more before it looks "well" shuffled.

Version 2: my fave. Start at the first position in the array. Pick a position at random. The random position will be between currentPosition..N-1. If the position picked is different than the current, swap. Move to the next position. Now the positions you're looking at will be 1..N-1. After that, 2..N-1, etc. Basically, after you assign a value to a current position, you move on and don't look back. You do this from 0..N-2.

Hope this helps.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1