2d文字配列をどのように並べ替えるか

Question

ここでは、特定の値を見つけるために2dのchar配列のすべての可能な組み合わせを使用する必要があるこの問題があります。

void permutate(int i, int r, int m, int factor, int count, char** danceRoutines); 

int main(void) 
{ 
    int routines, i, j, loop, factor, min, count = 0; 

    printf("Please enter the number of routines (min 2, max 10): \n"); 
    scanf("%d", &routines); 
    factor = factorial(routines); 

    //Check for routine < 2 and routine > 10 
    if(routines < 2 || routines > 10) 
    { 
     printf("Please, between 2 and 10 \n"); 
     return; 
    } 

    //Store the dancers they enter into a 2d array of size routines * MAX 
    char **danceRoutines = (char**)malloc(sizeof(char*) * routines); 
    for(i = 0; i < routines; i++) 
    { 
     char *s = (char*)malloc(sizeof(char)); 
     scanf("%s", s); 
     danceRoutines[i] = s; 
    } 

    min = quickChanges(danceRoutines, routines, 0); 
    printf("This is min: %d", min); 
    permutate(0, routines, min, factor, count, danceRoutines); 

    for(loop = 0; loop < routines; loop++) 
    { 
     free(danceRoutines[loop]); 
    } 

    free(danceRoutines); 
    return 0; 
} 

void permutate(int i, int r, int m, int factor, int count, char** danceRoutines) 
{ 
    int k, l, test, last; 
    if(last == 0) 
    { 
     printf("%d", m); 
    } 

    for(k = 0; k < r; k++) 
    { 
     int length = strlen(danceRoutines[k]); 
     char *line = (char*)malloc(sizeof(char) * length); 
     strcpy(line, danceRoutines[k]); 
     strcpy() 
     for(l = 1; l < factor/r; l++) 
     { 

     } 
    } 
} 

ファクタは、基本的に関数に読み込まれる整数rの階乗である。 2dのchar配列の順列を作成する簡単な方法はありますか？

Answer 1

通常の順列コードを使用します。文字列の文字をほとんど置き換えているにもかかわらず、おそらくSOの例はたくさんあります。

設定では、文字列はヒープ上に割り当てられ、それらのポインタによって表されます。今、あなただけのポインタスワップすることにより、文字列を入れ替えることができますので、それは、良いことだ：簡潔にするために

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



void permute(const char **str, size_t n, size_t i) 
{ 
    size_t j; 

    if (i == n) {   
     // permutation found: print the strings (or do other stuff) 
     for (j = 0; j < n; j++) { 
      if (j) printf(" "); 
      printf("%s", str[j]); 
     } 
     puts(""); 
    } else { 
     // recurse deeper with each of the remaining strings as next string 

     for (j = i; j < n; j++) { 
      const char *swap; 

      swap = str[i]; str[i] = str[j]; str[j] = swap; 
      permute(str, n, i + 1); 
      swap = str[i]; str[i] = str[j]; str[j] = swap; 
     } 
    } 
} 

int main(void) 
{ 
    const char *str[] = { 
     "red", "green", "blue", "white" 
    }; 

    permute(str, 4, 0); 

    return 0; 
} 

を、私はここに文字列リテラルを使用しましたが、あなたはあなたの例のようにstrdupまたはmallocとstrcpyを使用している場合、コードも同様に機能します。

char a[10][20]のような固定された文字列サイズを持つ実際の2次元配列を使用した場合は、周囲の文字列の内容をコピーしなければならず、コストがかかります。その場合、これらの文字列へのポインタを格納する2番目の配列を作成し、上記のように処理することをお勧めします。

（Ceterum censeo：私はまだあなたはすべての順列を作成する必要があることを確信していない）

編集：あなたはすべての隣接する文字列の間の最も少ない共通の文字との協定を探したい場合は、最初の場所で文字列を交換しないでください。代わりに：

• はw[i][j]は、文字列iとj間で共通の文字の数をハッシュマトリックスを作成します。
• 次に、{0, 1, 2, ..., n}で始まる整数のixed配列の順列を行います。
• あなたが行くにつれてペナルティの合計を累積します。並べ替えを見つけたら、それが最小かどうかを確認してください。
• 現在の合計を最小にすることができないことがわかっている場合、再帰の短縮をカットすることができます。

ので：

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

#define MAX 10 

int weight[MAX][MAX]; 
int best[MAX]; 
int min; 


void permute(int *perm, size_t n, size_t i, int sum) 
{ 
    size_t j; 

    if (sum >= min) return; 

    if (i == n) { 
     if (sum < min) { 
      min = sum; 
      memcpy(best, perm, n * sizeof(*perm)); 
     } 
    } else { 
     for (j = i; j < n; j++) { 
      int swap; 
      int w = 0; 

      if (i) w = weight[perm[i - 1]][perm[j]]; 

      swap = perm[i]; perm[i] = perm[j]; perm[j] = swap; 
      permute(perm, n, i + 1, sum + w); 
      swap = perm[i]; perm[i] = perm[j]; perm[j] = swap; 
     } 
    } 
} 

int common(const char *s, const char *t) 
{ 
    int res = 0; 

    while (*s && *t) { 
     if (*s == *t) { 
      res++; s++; t++; 
     } else { 
      if (*s < *t) s++; else t++; 
     } 
    } 

    return res; 
} 

void best_perm(const char **str, size_t n) 
{ 
    int perm[n]; 
    size_t i, j; 

    for (i = 0; i < n; i++) perm[i] = i; 

    for (i = 0; i < n; i++) { 
     for (j = 0; j < n; j++) { 
      weight[i][j] = weight[j][i] = common(str[i], str[j]); 
     } 
    } 

    min = INT_MAX; 

    permute(perm, n, 0, 0); 

    for (i = 0; i < n; i++) { 
     if (i) printf(" %d ", weight[best[i - 1]][best[i]]); 
     printf("%s", str[best[i]]); 
    } 
    printf("\nOverall penalty: %d\n", min);  
} 

int main(void) 
{ 
    const char *str[] = { 
     "acdeg", "acgh", "dg", "aeh", "cegh", 
     "abcfgh", "abc", "abc", "fgh", "abcdefgh" 
    }; 

    best_perm(str, 10); 

    return 0; 
} 

このソリューションは、まだ基本的にすべてのpemutationsをしようとすると、おそらく最適ではありません。重み行列をグラフ内の距離行列と考えるなら、グラフのための既知のpah-findingアルゴリズムのいずれかで問題に取り組むことができます。これは、経路が完全に丸くならない、荒れ狂うセールスマン問題のように見えます。