Creating Strings

Creating Strings

CSES easy

يُعطى لك نص. أنشئ كل النصوص المختلفة التي يمكن الحصول عليها بإعادة ترتيب حروفه.

القيود:

• \(1 \le n \le 8\)، حيث \(n\) طول النص
• يتكوّن النص من الحروف a–z فقط.

الإدخال:

• سطر واحد: النص.

المخرجات:

• السطر الأول: عدد صحيح \(k\) — عدد النصوص المختلفة.
• الأسطر الـ \(k\) التالية: النصوص بالترتيب الأبجدي.

مثال:

الإدخال:

aabac

المخرجات:

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

الحل

نبني النصوص بالتراجع (backtracking)، حرفًا بعد حرف. لو اخترنا في كل خطوة موقعًا من النص الأصلي، لأعطت الحروف المتساوية النص نفسه عدة مرات: للنص aabac عدد \(5! = 120\) ترتيبًا لمواقعه، لكن فيه \(20\) نصًا مختلفًا فقط.

لذلك نختار حروفًا بدلًا من المواقع. نعدّ كم نسخة من كل حرف في النص. في كل خطوة نجرّب كل حرف بقيت منه نسخة غير مستخدمة، فنستخدم نسخة واحدة، ونكمل، ثم نتراجع عن الخطوة. يُبنى كل نص مختلف مرة واحدة بالضبط، لأن اختيارين مختلفين في الخطوة نفسها يضعان حرفين مختلفين في الموقع نفسه.

نجرّب الحروف من a إلى z، لذلك تُنشأ النصوص بالترتيب الأبجدي.

عدد النصوص لا يزيد عن \(8! = 40320\)، لذلك يكون التراجع سريعًا.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n;
int available[26];  // how many copies of each letter are still unused
string current;
vector<string> result;

void backtracking() {
    // all letters are used, record the string
    if ((int) current.size() == n) {
        result.push_back(current);
        return;
    }

    // try each letter that is still available, in alphabetical order
    for (int c = 0; c < 26; c++) {
        if (available[c] == 0) {
            continue;
        }

        available[c]--;
        current.push_back('a' + c);
        backtracking();
        current.pop_back();  // undo the step
        available[c]++;
    }
}

int main() {
    string s;
    cin >> s;
    n = s.size();

    for (char ch : s) {
        available[ch - 'a']++;
    }

    backtracking();

    cout << result.size() << "\n";
    for (string t : result) {
        cout << t << "\n";
    }
}