• Status: Solved
• Priority: Medium
• Security: Public
• Views: 243

Random List

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
raza
• 9
• 8
• 6
• +1
1 Solution

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

Commented:
#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 Commented:
How do I keep the orignal values of a[].
0

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

Author Commented:
Yes...
0

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

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

0

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

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

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

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

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

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

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

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

Commented:
What randomness does it sacrifice?
0

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

Commented:
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 Commented:
how many bits should be for the a[500]?.
0

Commented:
/* 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

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

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.