?
Solved

Random List

Posted on 2003-03-21
24
Medium Priority
?
240 Views
Last Modified: 2010-04-15
I have the following number in a list. How do I randomly pick a number from list A and add it to list B and remove the randomly selected number from list A so it can not be pick again.


int a[10] = { 12 ,13, 34, 14, 43, 14, 32, 98, 23, 30};
int b[10]
0
Comment
Question by:raza
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 8
  • 6
  • +1
24 Comments
 
LVL 6

Accepted Solution

by:
gj62 earned 200 total points
ID: 8185441
#include<time.h>

int num;
srand(time(NULL)); /* call just ONCE to initialize*/

num = rand() % 10; /* gives you your index */

a[num] = random number from your array...
0
 
LVL 84

Expert Comment

by:ozo
ID: 8185469
#include <time.h>
#include <stdlib.h>
int a[10] = { 12 ,13, 34, 14, 43, 14, 32, 98, 23, 30};
int b[10];
int n,r;
srand(time(NULL));
for(n=10;n>0;n--){
    r = rand()%n;
    b[10-n] = a[r];
    a[r] = a[n-1];
}
for(n=0;n<10;n++){
    printf("%d ",b[n]);
}
0
 

Author Comment

by:raza
ID: 8185726
How do I keep the orignal values of a[].
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 84

Expert Comment

by:ozo
ID: 8185748
Do you mean you want to keep the randomly selected number in list A so it can be picked again?
0
 

Author Comment

by:raza
ID: 8186209
Yes...
0
 
LVL 6

Expert Comment

by:gj62
ID: 8186224
This will randomly populate b[] with elements from a[] - no repeats...

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


int a[10] = { 12 ,13, 34, 14, 43, 14, 32, 98, 23, 30};
int b[10];
int n,r;
srand(time(NULL));
  for( n=0; n<10; ++n)
  {
    do
    {
      r = rand() % 10;
    } while (a[r] == 0);
 
    b[n] = a[r];
    a[r] = 0;
  }
for(n=0;n<10;n++){
   printf("%d ",b[n]);
}
0
 

Author Comment

by:raza
ID: 8186229

When  you select a number from list A, It should not be select again by random selection.

0
 
LVL 6

Expert Comment

by:gj62
ID: 8186240
It won't be.

a[r] is set to = 0 once selected, and the while loop executes until it a[r] does not = 0.
0
 

Author Comment

by:raza
ID: 8186253

If you remove values from list a, you will not be able to genrate list B again or later if you need list C.
0
 
LVL 6

Expert Comment

by:gj62
ID: 8186269
True - but you said "remove the randomly selected number from list A", which this does by replacing it with 0.

If you need to keep the array intact, just copy it:

int a[10] = { 12 ,13, 34, 14, 43, 14, 32, 98, 23, 30};
int c[10];
memcpy(c, a, sizeof(a));

You can then work on c, and when you are done, repeat the memcpy to "reload" c with the values from a.
0
 

Author Comment

by:raza
ID: 8186281
Yes. I thought so too.

Is there any way I can do this without copying it to a new array because I will have memory limitation on the system where I need to save memroy as much as possible.


The thing I am trying to get it done will have about a[5000] or more.
0
 
LVL 6

Expert Comment

by:gj62
ID: 8186291
No,

If you can't change the values in a, you need to keep track somewhere of what has changed.

What type of system are you on?  

The reason I ask is that you could create a bitfield of 5000 bits (625 bytes), and set the bits on/off when they are selected, but that's a fair amount of work.

If you are working on 16-bit system, your array takes 10,000 bytes - not really all that much space.

0
 
LVL 6

Expert Comment

by:gj62
ID: 8186294
Well, there is another way...

You could scan b[] each time looking for the number, but since you can have repeated values in a[], you will also have to keep a counter of when you find a value.  If the counter < number of times that value appears, then you can select it...

Code in a moment...
0
 

Expert Comment

by:svatOpluk
ID: 8186569
Here is my suggestion for the code. I tried it and it works

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

#define NUM_ELEMENT 10
#define TRUE 1
#define FALSE 0

static void print_array(const int *a)
{
     int i;
     
     printf("ARRAY: ");
     for(i = 0; i < NUM_ELEMENT; ++i)
          printf("%d ", a[i]);
     printf("\n");
}

int main(void)
{
     int a[NUM_ELEMENT] = { 12 ,13, 34, 14, 43, 14, 32, 98, 23, 30};
     int b[NUM_ELEMENT];
     int *flag = calloc(NUM_ELEMENT, sizeof(int));
     int i = 0, randnum;
     
     srand((unsigned)time(NULL));

     while(i < NUM_ELEMENT)
     {
          randnum = rand() % 10;
          if(flag[randnum] == FALSE)
          {
               b[i] = a[randnum];
               flag[randnum] = TRUE;
               ++i;
          }
     }

     print_array(a);
     print_array(b);

     return 0;
}
0
 
LVL 84

Expert Comment

by:ozo
ID: 8186649
#include <time.h>
#include <stdlib.h>
int a[10] = { 12 ,13, 34, 14, 43, 14, 32, 98, 23, 30};
int b[10] ;
int n,r;
srand(time(NULL));
/* without replacement */
for(n=0;n<10;n++){
   b[n]=a[n];
}
for(n=1;n<10;n++){
    int t;
    r = rand()%n;
    t = b[n];
    b[n] = b[r];
    b[r] = t;
}
for(n=0;n<10;n++){
    printf("%d ",b[n]);
}
 printf("\n");
/* with replacement */
for(n=0;n<10;n++){
    int t;
    r = rand()%10;
    b[n] = a[r];
}
for(n=0;n<10;n++){
    printf("%d ",b[n]);}
0
 
LVL 6

Expert Comment

by:gj62
ID: 8186969
Raza:

svatOpluk's code uses the same memory as mine - it is just allocated on the heap.  If that's ok, great.

ozo's "without replacement" code randomizes the order in the array - which is great and memory efficient, but sacrifices a bit (but certainly not alot) of randomness.  

Here's code that copies the elements into the array, using a bit-array to keep track of those I've used.  Not as efficient as ozo's, but since I said I'd post the code here it is...

int findBit(int *bits, int r)
{
  if (bits[r>>3] & (1<<(r&0x07)))
  {
    return(1);  /* bit is set*/
  }
  bits[r>>3] = bits[r>>3]|1<<(r&0x07);
  return (0);
}


int main()
{  
  int a[5000];
  int b[5000];
  int bits[625];
  int x,n,r=0;
  memset(b, 0, sizeof(b));
  srand(time(NULL));

  /* fill with random numbers <100 */
  for(n=0;n<5000;n++)
  a[n] = rand() % 100;

  memset(bits,0,sizeof(bits));
  for( n=0; n<5000; ++n)
  {
    do
    {
      r = rand() % 5000;
    } while(findBit(bits,r));
 
    b[n] = a[r];
    printf("%d\r", n);
  }
 
  for(n=0;n<10;n++)
    printf("%d ",b[n]);
  return(0);
}
0
 
LVL 84

Expert Comment

by:ozo
ID: 8187234
What randomness does it sacrifice?
0
 

Author Comment

by:raza
ID: 8187459
I found there is a repetition of a values in  b.

The values of "a" should not be repeat in "b". If a value is already randomly selected then it should not be select again.
0
 

Author Comment

by:raza
ID: 8187489
Sorry to maintion this in earlier.


int a[25] = { 12 ,13, 34, 14, 43, 17, 32, 98, 23, 30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

The zeros are empty values which should not be selected when randomizing a values in b.
0
 
LVL 6

Expert Comment

by:gj62
ID: 8187721
Values are repeated ONLY if they appear twice in the array.  In your initial example, 14 is in the array twice.

Are you saying that if it is in the array more than once, it should only be included once?

To not use zero values, just test for them...

in my code above, add the if statement:

if (a[r] != 0)
{
  b[n] = a[r];
}

instead of just the assignment of b[n] = a[r].

ozo - b[0] is never explicitly swapped - you are relying on a random generation of a 0 to swap this value.  In fact, the smaller the value of n, the less random the swaps are over the size of the array.  If you look at the distribution of values through the array after your process, you'll find that they are not as even as they could be.  This could be dealt with if you did r = rand() % MAX_ELEMENTS.  It's not a big difference, like I said earlier...
0
 

Author Comment

by:raza
ID: 8187827
how many bits should be for the a[500]?.
0
 
LVL 84

Expert Comment

by:ozo
ID: 8188056
/* oops, you're right about it not being random, b[9] was never equal to a[9], here is the corrected routine */
for(n=1;n<10;n++){
    int t;
    r = rand()%(n+1);
    t = b[n];
    b[n] = b[r];
    b[r] = t;
}
0
 
LVL 6

Expert Comment

by:gj62
ID: 8188892
The number of bits of is whatever the size is divided by 8.  Add one if there is a remainder.

So for 500, there should be 62 bytes...
0
 
LVL 84

Expert Comment

by:ozo
ID: 8189013
If you want to remove duplicate and 0 values from b

#include <time.h>
#include <stdlib.h>
int compar(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}
main(){
int a[25] = { 12 ,13, 34, 14, 43, 17, 32, 98, 23, 30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int b[sizeof(a)/sizeof(a[0])] ;
int i,j,n,r,t;
srand(time(NULL));
for(n=0;n<(sizeof(a)/sizeof(a[0]));n++){
   b[n]=a[n];
}
/* remove duplicates */
qsort(b,n,sizeof(b[0]),&compar);
for( i=0,j=0,t=0; j<n; j++ ){
    if( (b[i]=b[j]) != t ){ i++; }
    t = b[j];
}
n = i;
/* shuffle */
for(i=1;i<n;i++){
    r = rand()%(i+1);
    t = b[i];
    b[i] = b[r];
    b[r] = t;
}
for(i=0;i<n;i++){
    printf("%d ",b[i]);
}
printf("\n");
}
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
Suggested Courses
Course of the Month14 days, 12 hours left to enroll

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question