คำอธิบายปัญหา
สมมติว่าเรามีสตริงหลายตัวในอาร์เรย์ เราต้องหาการจัดเรียง (Permutations) ทั้งหมดของสตริงเหล่านี้และแสดงผลแต่ละแบบในบรรทัดใหม่
ตัวอย่าง
หากอินพุตเป็น 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
- ใช้อัลกอริทึม Next Permutation มาตรฐาน:
- หา index i ที่ s[i] > s[i-1] จากท้ายสุด
- หา index j ที่ s[j] > s[i-1] จากท้ายสุด
- สลับ s[i-1] กับ s[j-1]
- กลับลำดับส่วนท้ายตั้งแต่ i ถึง n-1
- ใน main ใช้ do-while loop เรียก next_permutation() จนคืนค่า 0
- พิมพ์สตริงในแต่ละรอบคั่นด้วยช่องว่าง
โค้ดตัวอย่าง
#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;
}
อินพุต
{"abc", "def", "ghi"}
เอาต์พุต
abc def ghi abc ghi def def abc ghi def ghi abc ghi abc def ghi def abc
