พิมพ์การจัดเรียง (Permutations) ที่ไม่ซ้ำของสตริงที่มีตัวอักษรซ้ำใน C++

ภาพรวมปัญหา

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

ตัวอย่าง

Input: "XYZ"
Output: XYZ XZY YXZ YZX ZYX ZXY

วิธีแก้ปัญหา (Algorithm แบบ Dictionary Order)

1. เรียงตัวอักษรในสตริงก่อน
2. หา permutation ถัดไปในลำดับเล็กซิโคกราฟิกซ้ำๆ จนหมด
3. ขั้นตอนหา permutation ถัดไป:
   • หา index i ที่ str[i] < str[i+1] (จากขวาไปซ้าย)
   • หา ceil index (ตัวอักษรที่มากกว่า str[i] น้อยที่สุดทางขวา)
   • สลับ str[i] กับ str[ceilIndex]
   • เรียงส่วนท้าย (i+1 ถึงสุด) ใหม่

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

#include <string.h>
#include <iostream>
using namespace std;

int compare(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

void swapChar(char* a, char* b) {
    char t = *a; *a = *b; *b = t;
}

int findCeil(char str[], char first, int l, int h) {
    int ceilIndex = l;
    for (int i = l + 1; i <= h; i++)
        if (str[i] > first && str[i] < str[ceilIndex])
            ceilIndex = i;
    return ceilIndex;
}

void printPermutations(char str[]) {
    int size = strlen(str);
    qsort(str, size, sizeof(str[0]), compare);
    bool isFinished = false;
    while (!isFinished) {
        cout << str << "\t";
        int i;
        for (i = size - 2; i >= 0; --i)
            if (str[i] < str[i + 1]) break;
        if (i == -1) isFinished = true;
        else {
            int ceilIndex = findCeil(str, str[i], i + 1, size - 1);
            swapChar(&str[i], &str[ceilIndex]);
            qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare);
        }
    }
}

int main() {
    char str[] = "SNGY";
    cout << "All permutations of the string " << str << " are:\n";
    printPermutations(str);
    return 0;
}

ผลลัพธ์ (Output)

All permutations of the string SNGY are:
GNSY GNYS GSNY GSYN GYNS GYSN NGSY NGYS NSGY NSYG NYGS NYSG SGNY SGYN SNGY SNYG SYGN SYNG YGNS YGSN YNGS YNSG YSGN YSNG