固定文字列が期待通りに機能しない

Question

1つの単語のすべての可能な組み合わせを置換する関数を作成しようとしていますが、プログラムが置換文字列の複製を作成してしまいます。

この私の作業コードです：

#define _GNU_SOURCE 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

char arr[5000] = {0}; 
void swap (char *x, char *y); 
void permute(char *ptr, size_t i, size_t n); 

int main(void){ 
    char str[80] = "MICHI"; 
    size_t len = strlen(str); 

    permute(str, 0, len); 
    printf("%s\n", arr); 
    printf("END\n"); 
} 

void swap (char *x, char *y){ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *ptr, size_t i, size_t n){ 
    size_t j; 
    if (i == n){ 
     strcat (arr, ptr); 
     strcat (arr, "\n"); 
    }else{ 
     for (j = i; j <= n; j++) 
     { 

      swap((ptr + i), (ptr + j)); 
      permute(ptr, i+1, n); 
      swap((ptr + i), (ptr + j)); 
     } 
    } 
} 

そして、ここでは、出力されます。

ABC 
AB 
ACB 
AC 
A 
A 
BAC 
BA 
BCA 
BC 
B 
B 
CBA 
CB 
CAB 
CA 
C 
C 







END 

期待される成果は次のようになります。

ABC 
AB 
ACB 
AC 
A 
BAC 
BA 
BCA 
BC 
B 
CBA 
CB 
CAB 
CA 
c 

プログラムは、重複の多くを作成し、 2つ目のNew Linesも作成します。関数はpermuteで

IMCHI 
IMCH 
IMCIH 
IMCI 

Answer 1

あなたの順列で文字列の終端\0を含めています。

lineの内部状態は次のとおりです。

ABC\0 
AB\0C 
ACB\0 
AC\0B 
A\0CB 
A\0BC 
BAC\0 
BA\0C 
BCA\0 
BC\0A 
B\0AC 
B\0CA 
CBA\0 
CB\0A 
CAB\0 
CA\0B 
C\0AB 
C\0BA 
\0ABC 
\0ACB 
\0BAC 
\0BCA 
\0CAB 
\0CBA 

printfは0を終了するまで印刷されます。

修正する方法の1つは、ループの制限を1つ減らし、\0を置換から除外することです。 i番目の文字を除いた部分文字列を作成し、その部分文字列に対してpermuteを呼び出す2番目のループを追加する必要があります。

もう1つの方法は、ブランチが\0を超えたら置換を停止することです。

EDIT：ここ

は順列が前のものと同一である場合に出力を抑制することにより、「並び替え停止」に、第2の提案の実装です。

void permute(char *ptr, size_t i, size_t n){ 
    size_t j; 
    static char prev[80] = ""; 
    if (i == n){ 
     if (strcmp(prev, ptr)) { 
      strcat (arr, ptr); 
      strcat (arr, "\n"); 
      strcpy(prev, ptr); 
     } 
    }else{ 
     for (j = i; j <= n; j++) 
     { 

      swap((ptr + i), (ptr + j)); 
      permute(ptr, i+1, n); 
      swap((ptr + i), (ptr + j)); 
     } 
    } 
} 

Answer 2

あなたのループは、文字列のNULバイトが含まれています

はINPUTは、たとえばMICHIのためであれば、私はこのような重複を得ることに気づきました。 j <= nをj < nに変更するだけです。このよう ：

void permute(char *ptr, size_t i, size_t n){ 
    size_t j; 
    if (i == n){ 
     strcat (arr, ptr); 
     strcat (arr, "\n"); 
    }else{ 
     for (j = i; j < n; j++) 
     { 

      swap((ptr + i), (ptr + j)); 
      permute(ptr, i+1, n); 
      swap((ptr + i), (ptr + j)); 
     } 
    } 
}