Перестановка с разными элементами в каждой позиции

Question

у меня есть строка, я хочу из неё составить 2 перестановки, у которых будут различные элементы в каждой позиции.

Вот что я попытался сделать:

#include "bits/stdc++.h"

#define ll long long

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string A;
    cin >> A;

    int n = A.size();

    map<char, int> freq;

    for (int i = 0; i < n; i++) {
        freq[A[i]]++;
    }

    for (auto p : freq) {
        if (p.second > n / 2) {
            cout << "IMPOSSIBLE" << '\n';
            return 0;
        }
    }

    string B = A, C;

    while (n != C.size()) {
        C.clear();
        next_permutation(B.begin(), B.end());

        vector<bool> used(n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!used[j] && B[i] != A[j]) {
                    C += A[j];
                    used[j] = 1;
                    break;
                }
            }
        }
    }

    cout << B << '\n';
    cout << C << '\n';

    return 0;
}

Однако оно на некоторых строках очень долгое. Ограничение длины строки A 1000 символов.

Answer 1

Всем спасибо! Нашёл решение!

#include "bits/stdc++.h"

#define ll long long

using namespace std;

template <class S>
class BestShuffle {
public:
    BestShuffle() : rd(), g(rd()) {}

    S operator()(const S& s1) {
        S s2 = s1;
        shuffle(s2.begin(), s2.end(), g);
        for (unsigned i = 0; i < s2.length(); i++)
            if (s2[i] == s1[i])
                for (unsigned j = 0; j < s2.length(); j++)
                    if (s2[i] != s2[j] && s2[i] != s1[j] && s2[j] != s1[i]) {
                        swap(s2[i], s2[j]);
                        break;
                    }
        ostringstream os;
        os << s1 << endl << s2;
        return os.str();
    }

private:
    static int count(const S& s1, const S& s2) {
        auto count = 0;
        for (unsigned i = 0; i < s1.length(); i++)
            if (s1[i] == s2[i])
                count++;
        return count;
    }

    random_device rd;
    mt19937 g;
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string A;
    cin >> A;

    int n = A.size();

    map<char, int> freq;

    for (int i = 0; i < n; i++) {
        freq[A[i]]++;
    }

    for (auto p : freq) {
        if (p.second > n / 2) {
            cout << "IMPOSSIBLE" << '\n';
            return 0;
        }
    }

    BestShuffle<basic_string<char>> bs;

    cout << bs(A) << '\n';

    return 0;
}

БЛОГ НА HUSL

Перестановка с разными элементами в каждой позиции

Ответы (1 шт):