我想改组包含城市列表的数组以生成结果。这种改组的要求是，只有在至少六个不同的城市出现之后，同一城市才能再次出现。同一座城市只能出现两次。
之前我曾使用另一种情况弄乱了，但是我是这里的新手，已经习惯了如何发布自己正在苦苦挣扎的代码。任何帮助，将不胜感激。 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]);
}
最佳答案
该问题可以分两个步骤解决。
1）我们将辅助阵列改组以获得城市的初始位置。
我们可以使用FisherYates随机播放算法对初始数组进行随机播放。
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