与えられた文字列の順列を見つけるCプログラム

配列に文字列がほとんどないとします。それらのすべての順列を異なる行で見つける必要があります。

したがって、入力がstrings =["abc"、 "def"、 "ghi"]のような場合、出力は

abc def ghi
abc ghi def
def abc ghi
def ghi abc
ghi abc def
ghi def abc

これを解決するには、次の手順に従います-

• 関数next_permutation（）を定義します。これには、n個の文字列配列sが必要です。
• iを初期化する場合：=n-1、i> 0の場合、更新（iを1つ減らす）、次のようにします。
  • s [i]> s [i-1]）の場合、次のようになります。
    • j：=i + 1
  • j
  • s [j] <=s [i-1]）の場合、次のようになります。
    • ループから抜け出す
  • t：=s [i-1]
• s [i-1] =s [j-1]
• s [j-1] =t
• for i
• t：=s [i]
• s [i]：=s [n-1]
• s [n-1] =t

例

理解を深めるために、次の実装を見てみましょう-

#include <stdio.h>
#include <string.h>
int next_permutation(int n, char **s){
    for (int i = n - 1; i > 0; i--)
        if (strcmp(s[i], s[i - 1]) > 0){
            int j = i + 1;
            for (; j < n; j++)
                if (strcmp(s[j], s[i - 1]) <= 0)
                    break;
            char *t = s[i - 1];
            s[i - 1] = s[j - 1];
            s[j - 1] = t;
            for (; i < n - 1; i++, n--){
                t = s[i];
                s[i] = s[n - 1];
                s[n - 1] = t;
            }
            return 1;
        }
    for (int i = 0; i < n - 1; i++, n--){
        char *t = s[i];
        s[i] = s[n - 1];
        s[n - 1] = t;
    }
    return 0;
}
int main(){
    char *strings[] = {"abc", "def", "ghi"};
    int n = 3;
    do{
        for (int i = 0; i < n; i++)
            printf("%s%c", strings[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, strings));
}

入力

{"abc", "def", "ghi"}

出力

abc def ghi
abc ghi def
def abc ghi
def ghi abc
ghi abc def
ghi def abc