Chương trình C để tìm hoán vị của các chuỗi đã cho

Giả sử chúng ta có vài chuỗi trong một mảng. Chúng ta sẽ phải tìm tất cả các hoán vị của chúng trong một dòng khác nhau.

Vì vậy, nếu đầu vào giống như string =["abc", "def", "ghi"], thì đầu ra sẽ là

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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm next_permutation (), hàm này sẽ lấy n, mảng chuỗi s,
• để khởi tạo i:=n - 1, khi i> 0, hãy cập nhật (giảm i đi 1), thực hiện:
  • nếu s [i]> s [i - 1]), thì:
    • j:=i + 1
  • cho j
  • nếu s [j] <=s [i - 1]), thì:
    • Ra khỏi vòng lặp
  • t:=s [i - 1]
• s [i - 1] =s [j - 1]
• s [j - 1] =t
• đối với i
• t:=s [i]
• s [i]:=s [n - 1]
• s [n - 1] =t

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

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