Shuffling Arrays

This is a discussion on Shuffling Arrays within the C Programming forums, part of the General Programming Boards category; Part of a program I am working on needs to output a 4 digit number, in which none of the ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    2

    Shuffling Arrays

    Part of a program I am working on needs to output a 4 digit number, in which none of the digits are repeating. i.e 1135 and 1676 are not valid. Also, there can be no "0" in the 4 digit number.

    I defined an array:

    Code:
    int a ={1, 2, 3, 4, 5, 6, 7, 8, 9};
    for(i=0; i<4; i++)
       printf("%d", a[i]);
    and am trying to figure out a way to shuffle it and output a[0], a[1], a[2], and a[3].

    All advice is appreciated. Thanks in advance.

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    What you need is a "card shuffle". There are lots of variations but it can be done in a very simple loop...

    Code:
    // 100% untested
    
    #define MAX 10  // could be any number
    int array[MAX];
    int temp;
    int swap;
    
    // create sequence
    srand(time(0));  
    
    // shuffle in loop
    for (int i =  MAX; i > 0; i--)
      { swap = rand() % i;
         temp =  array[i];
         array[i] = array[swap];
         array[swap] = temp; }

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Take your array down to just 4 elements.

    Now imagine each element is a wheel on an odometer, beginning values of 1234:

    Now, 'drive' the wheels around, assigning digits of 1-9, but always working through the right most wheel, just like a real odometer:

    1234
    1235
    1236
    1237
    1238
    1239
    1240
    1241
    1242

    will produce every possible number. Test each number and see which one's are valid. If they are, output them, if not continue looping, until 9876.

    Each wheel can be a nested loop:

    Code:
    for(w1 = 1;w1<10;w1++) {
      for(w2 = 2;w2<9;w2++) { 
         etc., add two more wheels.
    
        
      }
    }
    And
    Welcome to the forum, ISUFrosh!


    If you only need "some" numbers, and they don't have to be in order, then the shuffling way is fine. This is more when you need ALL the numbers, and possibly, in order.

    Yes, I confess, I use this logic in my Sudoku solving program, so every digit among the candidate digits for that square, has to be checked.
    Last edited by Adak; 11-02-2010 at 11:34 PM.

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Wouldn't you want to go from 1 to 9 (inclusive) on all the indexes? You'll reject a lot of numbers starting with 11xx, but always starting at 2 from the second number means you'd jump from 1999 to 2211, missing valid combinations like e.g. 2134.

    You can also do this recursively. Something like (totally untested code and likely buggy code)

    Code:
    permute (unsigned char valid[10], unsigned char num[4], int pos)
    {
       if (pos == 4)
       {
          /* If it's a 4 digit number print it and return */
          printf ("%d%d%d%d\n", num[0] ... num[3]);
          return;
       }
       for (i = 0; i < 10; i++)
       { 
          /* For each valid remaining digits, display all of 
              the numbers which include each of those digits 
              at the current position.
            */
          if (valid[i])
          {
              valid[i] = 0;
              num[pos] = i + 1;
              permute(valid, num, pos+1)
              valid[i] = 1;
          }
       }
    }
    Initially set valid to all 1s and call it with pos = 0.

    It's overkill for this case, but nice because you can include/exclude all sorts of stuff by varying how valid[] is set up.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    2
    I think i figured something out, but can't get it to work.

    Code:
    #include <stdio.h>
    #include <time.h>
    
    int main()
    {
        int a[4];
        srand(time(NULL));
        int i,j, k=1;
    
          /*Initializes a[i], then compares it to a[j]. If they
             are equal, it should start over the while loop with 
              the same value fro 'i' until it is not equal to a[j]*/
    
           for(i=0;i<4;i++){
           while(k){
               a[i]=rand()%10;
               k=0;
               for(j=0;j<i; j++){
                   if(a[i] == a[j]);
                      k++;
                   }
           }
           k=1;
           printf("%d", a[i]);
           }
          
        system("pause");    
    }
    I have no clue why, but all i get is 1 digit, i.e. 1 or 5 or 3, and the command prompt is froze.


    Got it!!
    [code]
    a[0]=rand()%10;

    for(i=1; i<4; i++){
    a[i] = rand()%10;
    int temp = i;
    for(j=0; j<temp; j++){
    if(a[j]==a[i])
    i--;
    }
    } [\code]
    Last edited by ISUFrosh; 11-03-2010 at 04:37 PM.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Wouldn't you want to go from 1 to 9 (inclusive) on all the indexes? You'll reject a lot of numbers starting with 11xx, but always starting at 2 from the second number means you'd jump from 1999 to 2211, missing valid combinations like e.g. 2134.
    Exactly so. The 1234 was just a starting place.

    I'm not sure how many 4 digit numbers our guy needs, and whether they benefit by being in order, etc.

    That's a Freshman for ya!
    Last edited by Adak; 11-03-2010 at 08:34 PM.

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, 03:08 AM
  2. Replies: 16
    Last Post: 01-01-2008, 03:07 PM
  3. Need Help With 3 Parallel Arrays Selction Sort
    By slickwilly440 in forum C++ Programming
    Replies: 4
    Last Post: 11-19-2005, 09:47 PM
  4. Crazy memory problem with arrays
    By fusikon in forum C++ Programming
    Replies: 9
    Last Post: 01-15-2003, 08:24 PM
  5. shuffling arrays?
    By Munkey01 in forum C++ Programming
    Replies: 1
    Last Post: 01-12-2003, 04:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21