พิมพ์ Permutations ทั้งหมดที่ซ้ำตัวอักษรได้ใน C++

ในปัญหานี้ เราจะได้รับสตริง n ตัวอักษร และต้องพิมพ์ permutations ทั้งหมดของตัวอักษรของสตริง อนุญาตให้ซ้ำตัวอักษรของสตริง การพิมพ์ permutation ควรทำในลำดับอักษร (lexicographically sorted order)

ตัวอย่างเพื่อความเข้าใจ

Input - XY

Output - XX, XY, YX, YY

เพื่อแก้ปัญหานี้ เราต้องใช้ fix and recur logic ที่นี่ เราจะ fix องค์ประกอบหนึ่งที่ index แรกของ array แล้วเรียกซ้ำสำหรับองค์ประกอบถัดไปในลำดับ

มาดูตัวอย่างการ implement ที่จะทำให้คำตอบชัดเจนขึ้น

Input string XY

Fix first element at index 1: X_

Recursively call other elements and fill: XX → XY

Now fix next element at index 1: Y_

Recursively call other elements and fill: YX → YY

ตรรกะเดียวกันใช้ได้กับสตริงความยาว 3, 4, n

โปรแกรมตัวอย่าง

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

void printPermutations(char *str, char* permutations, int last, int index) {
    int i, len = strlen(str);
    for (i = 0; i < len; i++) {
        permutations[index] = str[i];
        if (index == last)
            cout << permutations << "\t";
        else
            printPermutations(str, permutations, last, index + 1);
    }
}

int main() {
    char str[] = "ABC";
    cout << "All permutations of the string with repetition of " << str << " are: " << endl;
    int len = strlen(str);
    char permutations[len];
    printPermutations(str, permutations, len - 1, 0);
    return 0;
}

ผลลัพธ์

All permutations of the string with repetition of ABC are:
AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC