เรียง Permutation แบบไม่ซ้ำพร้อม Duplicate ใน C++

โจทย์

ให้สตริงที่อาจมีตัวอักษรซ้ำ (และเรียงแล้ว) ต้องการพิมพ์ Permutation ทั้งหมดที่ไม่ซ้ำกัน แบบเรียงลำดับ

ตัวอย่าง: "AABC" → AABC, AACB, ABAC, ABCA, ACBA, ACAB, BAAC, BACA, BCAA, CABA, CAAB, CBAA

วิธีแก้ปัญหา

ใช้ Backtracking + Pruning:

1. เรียงสตริงก่อน (input มาเรียงแล้ว)
2. Fix ตัวแรก หา Permutation ของที่เหลือ
3. ข้ามการ swap ถ้าตัวอักษรซ้ำกับที่ fix ไปแล้ว (ฟังก์ชัน swaper)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool swaper(char str[], int start, int curr) {
    for (int i = start; i < curr; i++)
        if (str[i] == str[curr]) return 0;
    return 1;
}

void printPermutations(char str[], int index, int n) {
    if (index >= n) { cout << str << "\t"; return; }
    for (int i = index; i < n; i++) {
        bool check = swaper(str, index, i);
        if (check) {
            swap(str[index], str[i]);
            printPermutations(str, index + 1, n);
            swap(str[index], str[i]); // backtrack
        }
    }
}

int main() {
    char str[] = "AABC";
    int n = strlen(str);
    cout << "The string is: " << str << endl;
    cout << "The distinct sorted permutations are: \t";
    printPermutations(str, 0, n);
    return 0;
}

ผลลัพธ์

The string is: AABC
The distinct sorted permutations are: AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA