# randomizing arrays!!

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 08-01-2010
vulock_ka
randomizing arrays!!
im making a code for a deal or no deal game. and im having trouble randomizing the amounts in the briefcase. help me please. i need a code on c. my teacher said that its just like shuffling cards but i dont know how. please help me. :(
• 08-01-2010
KBriggs
Did you try anything at all?

rand - C++ Reference
• 08-02-2010
ignazioc
For i=0 TO n
K =rand(0,n)
Swap( array[i],array[k])
• 08-02-2010
msh
Quote:

Originally Posted by vulock_ka
im making a code for a deal or no deal game. and im having trouble randomizing the amounts in the briefcase. help me please. i need a code on c. my teacher said that its just like shuffling cards but i dont know how. please help me. :(

Well. I'd shuffle cards by doing the following.

Each card is a structure (struct) that would contains its suit, rank and a variable to hold a random integer value. I would store the deck in an array. Then I would generate and assign a random integer value to each card in the deck. When I'm done with that, I would sort all cards in ascending order of this random value.

Now I have a shuffled deck of cards. You can use the same principle to shuffle boxes in "Deal or No Deal" game.

This isn't something new I came up with, but rather a common technique. Google is your bestest friend.
• 08-02-2010
laserlight
Personally, I would go with what ignazioc suggested, except that I would use rand(i, n) and have one less iteration. Of course, you have to translate the pseudocode to actual C. The array would be an array of structs as msh suggested, except that you don't need "a variable to hold a random integer value".
• 08-02-2010
msh
Not that it is relevant for this case, but, logically, won't the randomness decrease as i approaches n?
• 08-02-2010
laserlight
Quote:

Originally Posted by msh
Not that it is relevant for this case, but, logically, won't the randomness decrease as i approaches n?

No, that just makes sure that elements already selected at random will not be selected again.
• 08-02-2010
KBriggs
Doing that, won't you only swap elements at the end of the array with elements that are quite near? And the last element would not get swapped at all unless it happened to get swapped before. If the briefcases were oringinally in increasing order, then they would tend to still be in that order after running through.

Since this is only happening once per game, I don't think efficiency is something to worry about.
• 08-02-2010
msh
Quote:

Originally Posted by KBriggs
Doing that, won't you only swap elements at the end of the array with elements that are quite near? And the last element would not get swapped at all unless it happened to get swapped before. If the briefcases were oringinally in increasing order, then they would tend to still be in that order after running through.

Since this is only happening once per game, I don't think efficiency is something to worry about.

That's what I was getting at. Sort of. Only you said it better. :)
• 08-02-2010
laserlight
Quote:

Originally Posted by KBriggs
Doing that, won't you only swap elements at the end of the array with elements that are quite near?

No, since the elements at the end of the array might get swapped with the elements that are in front early on.

Quote:

Originally Posted by KBriggs
And the last element would not get swapped at all unless it happened to get swapped before.

That is perfectly fine. In fact, in a way this is true of any element (notice that elements could get swapped with themselves, i.e., they might not change position: this means that given knowledge of an element's initial position, someone asked to guess its final position after the shuffle cannot eliminate its initial position as a possibility).

Quote:

Originally Posted by KBriggs
If the briefcases were oringinally in increasing order, then they would tend to still be in that order after running through.

Well, consider this: I give you a deck of cards in some given order. You select a card at random and place it on top of a pile. You select another card, besides the one already in the pile, at random and place it on top of the pile. You repeat this process until all the cards in the deck are in the pile. According to you, the cards in the pile will tend to be in the original order of the deck :)

Quote:

Originally Posted by KBriggs
Since this is only happening once per game, I don't think efficiency is something to worry about.

This is not about efficiency though: it is about removing bias from the shuffle. Admittedly, since this is only a student project, that is not something to worry about either, but it is indeed one way that I would approach the problem. (EDIT: I guess that it can be seen as being about efficiency though: this algorithm shuffles in O(n) time with O(1) additional space needed, whereas the algorithm that msh suggested shuffles in O(n log n) time if you use a comparison based sort, and requires O(n) additional space.)

Quote:

Originally Posted by msh
That's what I was getting at. Sort of. Only you said it better. :)

If you had taken your own advice implied by "Google is your bestest friend", you would have seen that my modification of ignazioc's suggestion turns it into a variant of a common shuffling algorithm :)
• 08-02-2010
KBriggs
If this were true, then we could randomize the array N times, and take the average of the elemetns of the array over all those times, and assuming that the briefcases were uniformly distributed, we would expect the averages to be equal in all the boxes, to the average of the initial entries in the case below.

If on the other hand, the list still had an increasing tendency, we would see that tendency in the averages, and the only box that would average to the expected value would be the 0th element that can swap with any element at all.

I whipped up this code:
It intializes an "ordered" 20 element array to the intengers 1 through 20. It then shuffles them as you siggested and takes the average of the shuffled array elements over 10,000,000 iterations.

I did this quite quickly so it is possible there is a mistake, but it suggests that there is still a tendency to order in your algorithm.

Code:

```#include <stdio.h> #include <stdlib.h> #include <time.h> #define ITER 10000000 #define CASES 20 void swap(double array[20],int i, int j) {   double temp;   temp=array[i];   array[i]=array[j];   array[j]=temp; } int main(void) {   srand(time(NULL));   double order[CASES]={0};   double shuffle[CASES]={0};   double total[CASES]={0};   int i,j;   int random;   for (i=0;i<CASES;i++)   {     order[i]=i;   }       for (j=0;j<ITER;j++)   {     for (i=0;i<CASES;i++)     {       random=rand()%(CASES-i)+i; //random number in [i,CASES]       shuffle[i]=order[random];       shuffle[random]=order[i];     }     for (i=0;i<CASES;i++)     {       total[i]+=shuffle[i];     }   }   for (i=0;i<CASES;i++)   {     total[i]/=(double) ITER;     printf("%g\n",total[i]);   }   return 0; }```
The output:

Code:

```9.49843 10.0004 10.5004 11.0009 11.5006 12.0014 12.5009 13.0019 13.4998 14.0019 14.4999 15.0005 15.4993 15.9996 16.5011 17.0002 17.4994 18.0003 18.4999 19```
• 08-02-2010
laserlight
Quote:

Originally Posted by KBriggs
I did this quite quickly so it is possible there is a mistake, but it suggests that there is still a tendency to order in your algorithm.

I think that there was indeed a mistake, e.g., you seem confused in your use of both shuffle and order arrays, and did not use your swap function at all. Try:
Code:

```#include <stdio.h> #include <stdlib.h> #include <time.h> #define ITER 10000000 #define CASES 20 void swap(double array[], int i, int j) {     double temp = array[i];     array[i] = array[j];     array[j] = temp; } int main(void) {     double numbers[CASES] = {0};     double totals[CASES] = {0};     int i, j;     srand(time(NULL));     for (i = 0; i < CASES; ++i)     {         numbers[i] = i;     }     for (j = 0; j < ITER; ++j)     {         /* Shuffle */         for (i = 0; i < CASES - 1; ++i)         {             swap(numbers, i, rand() % (CASES - i));         }         /* Add the value of each element to a corresponding running total */         for (i = 0; i < CASES; ++i)         {             totals[i] += numbers[i];         }     }     /* Print the mean of each running total */     for (i = 0; i < CASES; ++i)     {         printf("%g\n", totals[i] / ITER);     }     return 0; }```
• 08-02-2010
KBriggs
Oops, yes, I did not use swap - I did not need it. I do the shuffling in the loop using the third array.

However, I stand corrected.
• 08-02-2010
laserlight
Sorry, I realised that my code is wrong too: I made a mistake in the use of the swap function, and missed your idea. This is correct:
Code:

```#include <stdio.h> #include <stdlib.h> #include <time.h> #define ITER 10000000 #define CASES 20 void swap(double array[], int i, int j) {     double temp = array[i];     array[i] = array[j];     array[j] = temp; } int main(void) {     double numbers[CASES] = {0};     double totals[CASES] = {0};     int i, j;     srand(time(NULL));     for (j = 0; j < ITER; ++j)     {         /* Re-initialise the array */         for (i = 0; i < CASES; ++i)         {             numbers[i] = i;         }         /* Shuffle */         for (i = 0; i < CASES - 1; ++i)         {             swap(numbers, i, i + rand() % (CASES - i));         }         /* Add the value of each element to a corresponding running total */         for (i = 0; i < CASES; ++i)         {             totals[i] += numbers[i];         }     }     /* Print the mean of each running total */     for (i = 0; i < CASES; ++i)     {         printf("%g\n", totals[i] / ITER);     }     return 0; }```
Quote:

Originally Posted by KBriggs
Oops, yes, I did not use swap - I did not need it. I do the shuffling in the loop using the third array.

Yeah, now I understand your results: what you are doing is basically selecting elements from order and copying them into shuffle. Consider: suppose you select the last element from order and copy it into the first element of shuffle. You can never select the first element of order after that, but you might still select the last element of order again. In other words, your "shuffle" is not a shuffle at all, as the multiset (or bag) of elements of the result may be different from the multiset/bag of elements of the original.
• 08-02-2010
KBriggs
Right you are. I still am having trouble seeing how there is no order in shuffling increasingly small parts of an array, but results are results - I'll look in detail when I have more time.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last