In tất cả hoán vị theo thứ tự từ điển (lexicographic) trong C++

Cho chuỗi độ dài n, in tất cả hoán vị ký tự theo thứ tự bảng chữ cái.

Input: 'XYZ' Output: XYZ, XZY, YXZ, YZX, ZXY, ZYX

Giải pháp: Sắp xếp chuỗi tăng dần (hoán vị đầu tiên). Lặp sinh hoán vị tiếp theo (next_permutation logic).

Chương trình minh họa

#include <iostream>
#include <string.h>
using namespace std;
int compare(const void *a, const void *b){ return (*(char*)a - *(char*)b); }
void swap(char* a, char* b){ char t = *a; *a = *b; *b = t; }
int finduBound(char str[], char first, int l, int h){
    int ubound = l;
    for (int i = l+1; i <= h; i++)
        if (str[i] > first && str[i] < str[ubound]) ubound = i;
    return ubound;
}
void generatePermutaion(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 ubound = finduBound(str, str[i], i+1, size-1);
            swap(&str[i], &str[ubound]);
            qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare);
        }
    }
}
int main(){
    char str[] = "NOPQ";
    cout << "Hoán vị theo thứ tự từ điển:\n";
    generatePermutaion(str);
    return 0;
}

Kết quả

NOPQ NOQP NPOQ NPQO NQOP NQPO ONPQ ONQP OPNQ OPQN OQNP OQPN PNOQ PNQO PONQ POQN PQNO PQON QNOP QNPO QONP QOPN QPNO QPON