c - 数组的洗牌算法

Question

我想对包含城市列表的数组进行洗牌以生成结果。这种洗牌的要求是，至少出现了六个不同的城市后，才能再次出现同一个城市。同一城市只能出现两次。

我之前使用了不同的场景，但我是新来的，并且习惯了如何发布我正在努力解决的代码。任何帮助，将不胜感激。 Array5 是要打乱顺序的数组。

待洗牌的城市:

Boston, Durban, Melbourne, Paris, Denver, Algiers, Freetown, Sydney, Colorado, Oslo, Melbourne, Brussels

我已在下面添加了我的代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int i,j,count;

   char array1[3][10]={"Denver","Boston","Colorado"};
   char array2[3][10]={"Melbourne","Sydney","Canberra"};
   char array3[3][10]={"Paris","Brussels","Oslo"};
   char array4[3][10]={"Durban","Algiers","Freetown"};

   char array5[12][10];

   for (i=0;i<3;i++){
       strcpy(array5[i],array1[i]);
   }

   for (i=0;i<3;i++){
       strcpy(array5[i+3],array2[i]);
   }

   for (i=0;i<3;i++){
       strcpy(array5[i+6],array3[i]);
   }

   for (i=0;i<3;i++){
       strcpy(array5[i+9],array4[i]);
   }

   for (i=0;i<12;i++)
       printf("%s\t\n",array5[i]);
}

Answer 1

这个问题可以分两步解决。

1) 我们对辅助数组进行打乱以获得城市的初始位置。

我们可以使用 FisherYates shuffle 算法来对初始数组进行洗牌。

2)我们随机决定要复制哪个城市。我们必须注意这些限制。城市只能翻倍一次。如果城市加倍，那么它们之间至少有 6 个城市。

代码中的更多解释:

// The requirement for this shuffling is that same city can only appear again after at least six different cities have appeared.
// A city can only appear twice.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define STR_LEN                 16
#define NR_OF_ROWS               3
#define NR_OF_SMALL_ARRAYS       4
#define NR_OF_ROWS_IN_BIG_ARRAY  NR_OF_ROWS*NR_OF_SMALL_ARRAYS

#define DOUBLE_COUNTER          12 // number of tries to double the city

void copy(char dest[][STR_LEN], char source[][STR_LEN], size_t displacement)
{
    size_t i;
    for (i=0; i<NR_OF_ROWS; i++){
      strcpy(dest[i+displacement], source[i]);
    }
}   

void init_shuffle(size_t array[], size_t size)
{
    size_t i;

    for (i=0; i<size; i++){
        array[i] = i;
    }
}

void print_array(char array[][STR_LEN], size_t size)
{
    size_t i;
    for (i=0; i<size; i++){
         printf("%s ",array[i]);
    }
    printf("\n");
}

void print_shuffle(size_t array[], size_t size)
{
    size_t i;
    for (i=0; i<size; i++){
         printf("%zu ",array[i]);
    }
    printf("\n");
}

void print_corresponding_cities(char array[][STR_LEN], size_t *shuffle, size_t size)
{
    size_t i;
    size_t j;

    for (i=0; i < size; i++){

        j = shuffle[i];

        printf("%s ", array[j] );
    }
    printf("\n");
}

int check_for_repeats(size_t *arr, size_t size, size_t value)
{
    size_t i;
    size_t counter = 0;
    for (i=0; i<size; i++){

       if(arr[i] == value){

           counter++;
           if(counter > 1)
              return 1;  // repeats found
       }  
    }
    return 0;  // no repeats       
}

int check_for_number_of_repeats(char array[][STR_LEN], size_t *arr, size_t size)
{
    size_t i, j;
    size_t counter = 0;
    size_t value;
    int repeats = 0;

    for (j=0; j<size; j++){    

        value = j;
        counter = 0;

        for (i=0; i<size; i++){

            if(arr[i] == value){

                counter++;

               if(counter > 1){
                  repeats++;               // repeats found
                  printf("%s ", array[j]); // print the city
                  break;
               }
            }
        }  
    }
    return repeats;          
}    

void FisherYatesShuffle(size_t *arr, int n) { 

     size_t i, j; // indexes
     size_t tmp;  // create local variables to hold values for shuffle

     for (i = n - 1; i > 0; i--) {  // shuffle
         j = rand() % (i + 1);      // randomise j for shuffle
         tmp = arr[j];
         arr[j] = arr[i];
         arr[i] = tmp;
     }
}

int main()
{
    size_t i;
    int no_yes;
    size_t double_index;
    time_t t;

    size_t shuffle[NR_OF_ROWS_IN_BIG_ARRAY]; // keep the results

    char array1[NR_OF_ROWS][STR_LEN]={"Denver0","Boston1","Colorado2"};
    char array2[NR_OF_ROWS][STR_LEN]={"Melbourne3","Sydney4","Canberra5"};
    char array3[NR_OF_ROWS][STR_LEN]={"Paris6","Brussels7","Oslo8"};
    char array4[NR_OF_ROWS][STR_LEN]={"Durban9","Algiers10","FreeTown11"};
    char array5[NR_OF_ROWS_IN_BIG_ARRAY][STR_LEN];

    init_shuffle(shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    // Initial arrangement:
    copy(array5, array1, 0*NR_OF_ROWS);
    copy(array5, array2, 1*NR_OF_ROWS);
    copy(array5, array3, 2*NR_OF_ROWS);
    copy(array5, array4, 3*NR_OF_ROWS);

    printf("Initial arrangement:\n");
     print_shuffle(shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    print_array(array5, NR_OF_ROWS_IN_BIG_ARRAY);

    printf("\n");

    // Algorithm: 
    // Note:
    // The shuffling will be done on the auxilliary shuffle array
    // Once the shuffling is done we can print the cities base on shuffle array values

    // Steps.
    // 1. We shuffle existing cities.

    // 2. We randomly decide if we want to repeat the city.
    // 3. If yes, we choose a random city 
    //
    // 4. Now we have to repeat that city. The requirement is that if we repeat the city
    // then we have have at least 6 cities between them.
    // E.g. We want to repat city from index 0 then duplicated city can only be placed at index 7 to 11

    // Index Next city placement:
    //
    // 0     7-11  range 5     [7,8,9,10,11]
    // 1     8-11  range 4 
    // 2     9-11  range 3
    // 3     10-11 range 2   
    // 4     11 fixed position 
    // 5     no placement
    // x     if (x > 4) no placement possible
    //       else placement possible in the range  [x+7, 11] 
    //       size of the range is 5-x
    // 5. we can repeat that procees a few times (DOUBLE_COUNTER). Restriction: A given city can be repeated only 1 time.

    /* Intializes random number generator */
    srand((unsigned) time(&t));

    // 1. Shuffle
    printf("After the shuffle:\n");
    FisherYatesShuffle(shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    print_shuffle(shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    print_corresponding_cities(array5, shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    printf("\n");

    // 2. Add cities
    for(int i=0; i < DOUBLE_COUNTER; i++)
    {
        no_yes = rand() % 2; //  add? YES OR NO 

        if(no_yes == 0)      // NO
            continue;

        double_index = rand() %  NR_OF_ROWS_IN_BIG_ARRAY; // which city 

        if(double_index > 4)
             continue;      // NO placement possible

        // check for repeats
        int rep = check_for_repeats(shuffle, NR_OF_ROWS_IN_BIG_ARRAY, shuffle[double_index]); 

        if(rep)
           continue; // city under this index has a double already 

        //-------------------------------------------------------   
        // OK we need to repeat the city
        if(double_index == 4)
        {
            shuffle[11] = shuffle[double_index];
            continue;
        }

        // now we have a choice:
        int choice = rand() % (5 - double_index);

        // random placement within the range:

        shuffle[double_index +7 + choice] = shuffle[double_index];
        //-------------------------------------------------------
    }

    // Results:

    printf("Final arrangement after adding double city/cities:\n");
    print_shuffle(shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    print_corresponding_cities(array5, shuffle, NR_OF_ROWS_IN_BIG_ARRAY);

    // Stats:
    printf("\nThese cites occure two times:\n");    
    int nr_rep = check_for_number_of_repeats(array5, shuffle, NR_OF_ROWS_IN_BIG_ARRAY);
    printf("\nNumber of repeated cities = %d\n", nr_rep);

    return 0;
}

输出:

Initial arrangement:                                                                                                                             
0 1 2 3 4 5 6 7 8 9 10 11                                                                                                                        
Denver0 Boston1 Colorado2 Melbourne3 Sydney4 Canberra5 Paris6 Brussels7 Oslo8 Durban9 Algiers10 FreeTown11                                       

After the shuffle:                                                                                                                               
5 9 3 11 6 8 4 0 7 2 1 10                                                                                                                        
Canberra5 Durban9 Melbourne3 FreeTown11 Paris6 Oslo8 Sydney4 Denver0 Brussels7 Colorado2 Boston1 Algiers10                                       

Final arrangement after adding double city/cities:                                                                                               
5 9 3 11 6 8 4 0 5 2 1 6                                                                                                                         
Canberra5 Durban9 Melbourne3 FreeTown11 Paris6 Oslo8 Sydney4 Denver0 Canberra5 Colorado2 Boston1 Paris6                                          

These cites occure two times:                                                                                                                    
Canberra5 Paris6                                                                                                                                 
Number of repeated cities = 2