Thread: randomizing arrays!!

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    1

    Unhappy 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. #2
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    Did you try anything at all?

    rand - C++ Reference

  3. #3
    Registered User
    Join Date
    Feb 2010
    Posts
    11
    For i=0 TO n
    K =rand(0,n)
    Swap( array[i],array[k])

  4. #4
    Novice
    Join Date
    Jul 2009
    Posts
    568
    Quote Originally Posted by vulock_ka View Post
    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. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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".
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Novice
    Join Date
    Jul 2009
    Posts
    568
    Not that it is relevant for this case, but, logically, won't the randomness decrease as i approaches n?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    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. #9
    Novice
    Join Date
    Jul 2009
    Posts
    568
    Quote Originally Posted by KBriggs View Post
    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. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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
    Last edited by laserlight; 08-02-2010 at 09:34 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    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
    Last edited by KBriggs; 08-02-2010 at 09:53 AM.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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;
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    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. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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.
    Last edited by laserlight; 08-02-2010 at 10:27 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to create and manipulate Terabyte size Arrays with Win32API
    By KrishnaPG in forum Windows Programming
    Replies: 1
    Last Post: 11-05-2009, 04:08 AM
  2. pointers & arrays and realloc!
    By zesty in forum C Programming
    Replies: 14
    Last Post: 01-19-2008, 04:24 PM
  3. Replies: 16
    Last Post: 01-01-2008, 04:07 PM
  4. Need Help With 3 Parallel Arrays Selction Sort
    By slickwilly440 in forum C++ Programming
    Replies: 4
    Last Post: 11-19-2005, 10:47 PM
  5. Crazy memory problem with arrays
    By fusikon in forum C++ Programming
    Replies: 9
    Last Post: 01-15-2003, 09:24 PM

Tags for this Thread