Генерация перестановок

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

fstream fout;

void printA(const vector<short int> &arr) {
    short int len = arr.size();
    for (int i = 0; i < len - 1; ++i) {
        cout << arr[i] << " ";
    };
    cout << arr[len - 1] << endl;
}

void generate(vector<short int> &A)
{
    short int p, q, i, k, m, min, tmp;
    short int n = A.size();
    bool end = false;
    while (!end) {
        printA(A);
        p = 0; 
        // Ищем крайний справа A[p], такой, что A[p] < A[p+1] 
        /*
        for (i = n - 1; i >= 1; --i) {
            if (A[i - 1] < A[i]) {
                p = i - 1;
                cout << p << endl;
                break;
            }
        }
        */

        i = n - 2;
        while (i >= 0) {
            if (A[i + 1] > A[i]) {
                p = i;
                break;
            }
            --i;
        }
        //cout << "A[p] = " << A[p] << " A[p+1] = " << A[p+1] << endl;

        if (i < 0) {
            return;
        }

        // Ищем минимальный A[q] среди A[p+1], ..., A[n], такой, что A[q] > A[p]
        min = A[p + 1];
        q = p + 1;
        for (i = p + 1; i < n; ++i) {
            if ((min > A[i]) && (A[i] > A[p])) {
                min = A[i];
                q = i;
            }
        }

        //cout << "q = " << q << " min = " << min << endl;

        // Меняем местами A[p] и A[q]
        std::swap(A[p], A[q]);

        //cout << "Swap " << A[p] << " - " << A[q] << endl;

        // Инвертируем A[p+1], ..., A[n]
        std::reverse(A.begin() + (p + 1), A.end());
    }
}

int main()
{
    short int n;

    cin >> n;

    fout.open ("output.txt", fstream::out);

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

    generate(A);

    //system("pause");
    return 0;
}