c - 随机打乱一组字符串

Question

我正在编写一个程序，它读取一个文本文件作为输入，并为用户随机打乱字符串数组。 我编写了一个随机打乱字符串数组的程序，但我想以一种没有两个相同的元素彼此相邻的方式进行。

举个例子: 原始数组看起来像这样

{1,2,3,4,5,1,2}

打乱后的数组看起来像这样

{5,3,1,2,4,2,1}

但目前我的程序创建了一个输出数组

{5,1,1,3,2,4,2}

这是我随机打乱元素的代码:

int i;  
char s[11][100];
char line[100], t[100];

/*Open the text file*/
FILE *fp;
fp = fopen("players.txt", "r");

/*Read each line and put it into an element in an array.
Each line will be in a seperate element in the array.*/
i=0;
while(fgets(line, 100, fp)!= NULL){
    strcpy(s[i], line);
    i++;

}


/*Generates a random number stored in j and shuffles the order of the array randomly*/
for(i=1; i<10; i++){

    j = rand()%(i+1);
    strcpy(t, s[j]);
    strcpy(s[j], s[i]);
    strcpy(s[i], t);    

}

Answer 1

据我所知，没有比重复运行 Fisher-Yates 随机播放直到找到没有相邻重复项的排列更好的解决方案了。 (这通常称为拒绝策略。)

这将花费的时间取决于随机洗牌具有相邻重复项的概率，如果重复项很少，则该概率会很低，如果集合的一半以上是相同的多数元素，则可能高达 1.0 .由于如果没有可能的合格安排，拒绝策略永远不会终止，因此值得麻烦验证解决方案是否可行，这意味着不存在多数元素。如果需要，可以使用 O(n) 算法，但考虑到您提供的精确细节，(目前)应该没有必要。

您可以立即拒绝而不是继续洗牌结束，这样可以显着降低运行算法的成本。因此，只需使用您的洗牌算法，但如果您将一个元素放在它的双胞胎之一旁边，则重新启动计数器。

顺便说一下，使用strcpy 来移动元素确实效率很低。只需打乱指针即可。

这是一些改编自 this answer 的代码.为简单起见，我假设重复项是准确的；或许你有其他的表达方式(比如只看第一个词):

void shuffle(const char* names[], size_t n) {
  for (size_t i = 0; i < n;) {
    size_t j = i + rand() % (n - i);
    /* Reject this shuffle if the element we're about to place
     * is the same as the previous one
     */
    if (i > 0 && strcmp(names[j], names[i-1]) == 0)
      i = 0;
    else {
      /* Otherwise, place element i and move to the next one*/
      const char* t = names[i];
      names[i] = s[j];
      names[j] = t;
      ++i;
    }
  }
}

对于您的用例，如果您有 10 个对象，频率分别为 3、3、2 和 2，则有 605,376 个有效排列，总共 3,628,800(10!)个排列，因此每六次洗牌中大约有五次将在之前被拒绝平均而言，您会找到一个有效的安排。然而，提前终止意味着你将做不到单次洗牌工作量的六倍；经验结果表明，大约需要 33 次交换才能产生具有上述频率的 10 个对象的有效洗牌。

注意:rand()%k 不是生成从 0 到 k-1 的整数均匀分布的好方法。您会在本网站上找到很多相关建议。