# randomizing arrays!!

This is a discussion on randomizing arrays!! within the C Programming forums, part of the General Programming Boards category; im making a code for a deal or no deal game. and im having trouble randomizing the amounts in the ...

1. ## 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.

2. Did you try anything at all?

rand - C++ Reference

3. For i=0 TO n
K =rand(0,n)
Swap( array[i],array[k])

4. 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.

5. 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".

6. Not that it is relevant for this case, but, logically, won't the randomness decrease as i approaches n?

7. 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.

8. 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.

9. 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.

10. 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.

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).

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

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.)

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

11. 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```

12. 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;
}```

13. 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.

14. 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;
}```
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.

15. 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.

Page 1 of 2 12 Last