Giả sử chúng ta có một mảng chứa vài chuỗi. Nhiệm vụ là tìm tất cả các hoán vị của chúng và in mỗi hoán vị trên một dòng riêng.
Ví dụ, nếu đầu vào là strings = ["abc", "def", "ghi"], thì đầu ra sẽ là tất cả 6 hoán vị:
abc def ghi abc ghi def def abc ghi def ghi abc ghi abc def ghi def abc
Giải thuật
- Triển khai hàm next_permutation() theo thuật toán hoán vị tiếp theo (next permutation)
- Tìm chỉ số i lớn nhất sao cho s[i] > s[i-1]
- Tìm chỉ số j lớn nhất sao cho s[j] > s[i-1]
- Hoán đổi s[i-1] và s[j-1]
- Đảo ngược đoạn từ i đến cuối mảng
- Trong main: in hoán vị hiện tại, sau đó lặp next_permutation() cho đến khi trả về 0
Ví dụ minh họa
#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));
return 0;
}
Đầ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