In Tất Cả Hoán Vị Riêng Biệt Của Chuỗi Có Ký Tự Trùng Lặp Trong C++

Trong bài toán này, chúng ta được cho một chuỗi có thể chứa ký tự trùng lặp. Nhiệm vụ là in tất cả các hoán vị riêng biệt của chuỗi.

Ví dụ để hiểu vấn đề:

Đầu vào: chuỗi = "XYZ" → Đầu ra: XYZ XZY YXZ YZX ZYX ZXY

Để giải quyết, ta cố định một phần tử của chuỗi. Sau đó lặp qua tất cả các phần tử của chuỗi.

Ví Dụ

Chương trình triển khai giải pháp:

#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) {
        static int x = 1;
        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 << "Tất cả hoán vị của chuỗi " << str << " là:\n";
    printPermutations(str);
    return 0;
}

Đầu Ra

Tất cả hoán vị của chuỗi SNGY là: GNSY GNYS GSNY GSYN GYNS GYSN NGSY NGYS NSGY NSYG NYGS NYSG SGNY SGYN SNGY SNYG SYGN SYNG YGNS YGSN YNGS YNSG YSGN YSNG