如何避免两个相同的第一个字母在洗牌中彼此相邻的句子？

Question

我有一段代码，我已经编写了一个混音音轨的文本文件，我如何调整我的代码，以便每次运行该程序时，都不会有两个音轨旁边的音轨开头第一封信。例如，艺术家Hozier的两首曲目不应该彼此相邻。

正确：

Hozier - Take Me To Church 
Pink - So What 
Hozier - Cherry Wine 

错误：

Hozier - Take Me To Church 
Hozier - Cherry Wine 
Pink - So What 

这里是我的代码：

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

// Accepts: command line input 
// Returns: 0 if no error 

int main(int num_args, char *arg_strings[]) 
{ 
    int x = 0, i, track_count = 0; 
    unsigned long Max_Length = 0; 
char line[500], *temp; 
FILE *file = fopen("InputFiles/playlist.txt", "r"); 
/* The next line checks if the playlist file exists and if it's not there, "Cannot Open File" is printed to the screen */ 
if (file == NULL){ 
    printf("Cannot open file\n"); 

} 
/* The following code identifies each line in the text and lines are shuffled accordingly */ 

while (fgets(line, sizeof(line), file) != NULL) 
{ 
    track_count++; 
    if (strlen(line) > Max_Length) 
     Max_Length = strlen(line); 
} 
rewind(file); 
char *Array[track_count]; 
while (fgets(line, sizeof(line), file) != NULL) 
{ 
    Array[x] = malloc(strlen(line)); 
    if (Array[x] == NULL){ 
     printf("A memory error occurred.\n"); 
     return(1); 
    } 
    strcpy(Array[x], line); 
    /* change \n to \0 */ 
      Array[x][strlen(Array[x])-1] = '\0'; 
      x++; 
     } 

    printf("The original playlist is:\n"); 
    for (x = 0; x < track_count; x++) 
    printf("%2d %s\n", x, Array[x]); 
/* The array will now be shuffled: */ 
srand((unsigned int) time(NULL)); 
for (x = track_count - 1; x >= 0; x--){ 
    i = (int) rand() % track_count; 
    temp = Array[x]; 
    Array[x] = Array[i]; 
    Array[i] = temp; 
} 
printf("\nShuffled Array\n"); 
for (x = 0; x < track_count; x++) 
    printf("%2d %s\n", x, Array[x]); 

return 0; 
} 

Answer 1

我与某事想出了这个样子，似乎工作，但理念有待提高（如果所有曲目都以相同的字母开头，那么可以添加一些尝试的限制）

for (x = track_count - 2; x > 1; x--){ 
    while(1) 
    { 
     i = rand() % (track_count - 1) + 1; 
     if(Array[x+1][0] == Array[i][0]) 
      continue; 
     if(Array[x-1][0] == Array[i][0]) 
      continue; 
     if(Array[i+1][0] == Array[x][0]) 
      continue; 
     if(Array[i-1][0] == Array[x][0]) 
      continue; 

     temp = Array[x]; 
     Array[x] = Array[i]; 
     Array[i] = temp; 
     break; 
    } 
} 

Answer 2

以下函数“isValidOrder”检测歌曲是否以有效顺序混洗。它使用序列“ - ”作为艺术家的分隔符。如果检测到无效订单或可能想要修改此代码，则可能只是想要再次对歌曲进行随机播放。像这样使用它：“isValidOrder（Array，track_count）”。如果订单是有效的，则返回1 - 否则为0

int isSameArtist(char * artist1, int artist1Length, char * artist2, int artist2Length){ 
    if (artist1Length != artist2Length) { 
     return 0; 
    } 
    for (int i = 0; i < artist1Length; i++) { 
     if (artist1[i] != artist2[i]) { 
      return 0; 
     } 
    } 
    return 1; 
} 

int getLengthOfArtist(char * title){ 
    int length = 0; 
    while (*title != '\0') { 
     if(title[0] == ' ' && title[1] != '\0' && title[1] == '-' && title[2] != '\0' && title[2] == ' '){ 
      return length; 
     }else{ 
      title ++; 
      length ++; 
     } 
    } 
    return length; 
} 

int isValidOrder(char ** Array, int track_count){ 
    if (track_count == 0) 
     return 1; 
    char * artist = Array[0]; 
    int artistLength = getLengthOfArtist(artist); 
    for (int i = 1; i < track_count; i++) { 

     char * nextArtist = Array[i]; 
     int nextArtistLength = getLengthOfArtist(nextArtist); 
     if (isSameArtist(artist, artistLength, nextArtist, nextArtistLength) == 1) { 
      return 0; 
     } 
     artist = nextArtist; 
     artistLength = nextArtistLength; 
    } 
    return 1; 
} 

Answer 3

如果同一首歌曲的重复被允许（例如，当一个音乐播放器是在两个随机播放和重复），你可以只记得以前第一个字母，然后从那些没有与前一首歌曲相同的第一个字母中随机选取每首连续的歌曲。

然而，洗牌的歌曲不重复，只考虑最后的位置不能正常工作，例如，如果你的歌曲有首字母C A C B C A C，他们最终可能作为A B A C C C C在你只有C -songs其余在年底。您可以检测到这种情况（即，不是从前一首字母开始的未混杂歌曲的数量为零），并且在这些情况下，在先前排序的列表中找到可插入每首新歌曲的位置，并从中随机选取。例如，如果您有上述第一个字母并且位于A B A C，则以C开头的下一首歌曲可以插入3个不同的位置（C A B A C,A C B A C或A B C A C）。

Answer 4

使用256个桶子列表。

如果可以，我会尝试编码。认为算法值得发布。

伪代码：

1. 输入n数据转换成256 1的列表Array[first letter][]。

2. 步骤将在每一个优先级队列非空列表为3

3. 认沽列出了到基于列表项中的最大＃列表的优先级队列。

4. 从队列中提取最大列表，将其称为G1。从列表中删除1项并放入ArrayB[]。

5. 从队列中提取最大列表，称之为G2。从列表中删除1项并放入ArrayB[]。

6. 如果不为空，则将G1放回优先级队列。

7. G2现在变成G1。

8. 继续执行第5步，直到队列为空。

9. 继续步骤7，直到G2空。

10. 在这一点上，我们现在有一个列表ArrayB[]，虽然不是随机的，如果可能的话，符合标准。

11. 经过ArrayB[]，比如3*n次，如果交换满足无重复条件，则随机交换一对itmes。