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.
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.
Did you try anything at all?
rand - C++ Reference
For i=0 TO n
K =rand(0,n)
Swap( array[i],array[k])
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.
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".
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.Originally Posted by msh
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
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
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
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 deckOriginally Posted by KBriggs
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 KBriggs
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 algorithmOriginally Posted by msh
Last edited by laserlight; 08-02-2010 at 10:34 AM.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
The output: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; }
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
Last edited by KBriggs; 08-02-2010 at 10:53 AM.
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:Originally Posted by KBriggs
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; }
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
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; }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.Originally Posted by KBriggs
Last edited by laserlight; 08-02-2010 at 11:27 AM.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.