如何避免兩個相同的第一個字母在洗牌中彼此相鄰的句子？

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。