// BMI.cpp : generowanie permutacji poprzez najmniejsza ilosc transpozycji
//

// kompilacja: g++ BMI.cpp -o BMI -std=c++11

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <cmath>

/* BMI zdefiniowane wg algorytmu 8 */
int bmi(int m, int i) {
    if ((m % 2 == 0) && (m > 2))
        if (i < m - 1)
            return i;
        else return m - 2;
    else return m - 1;
}

void perm(int m, std::vector<int> &p) {
    // vector pomocniczy
    auto fill_help = [&]() { std::vector<int> res;  for (auto i = 0; i < m; i++) res.push_back(0); return res; };
    auto help = fill_help();
    auto x = 1;

    // wypisz 1sza permutacje
    for (auto i = 0; i < p.size(); ++i) {
        std::cout << p[i] << " ";
    }
    std::cout << std::endl;

    // generuj reszte permutacji
    while (x < m) {
        if (help[x] < x) {
            auto tmp = p[x];

            // test zmodyfikowanej wersji bmi, rowniez generuje permutacje ale w innej kolejnosci
            //auto bmi = x - 2 < 0 ? x - 1 : x - 2;
            /*p[x] = p[bmi];
            p[bmi] = tmp;*/

            p[x] = p[bmi(x, help[x])];
            p[bmi(x, help[x])] = tmp;

            for (auto i = 0; i < p.size(); ++i) {
                std::cout << p[i] << " ";
            }
            std::cout << std::endl;

            help[x]++;
            x = 1;
        }
        else {
            help[x] = 0;
            x++;
        }
    }
}

int main()
{
    // tablica globalna (prawie) nigdy nie jest dobrym pomyslem
    std::vector<int> p;
    int ile;

    std::cout << "Ile elementow ma miec zbior?" << std::endl;
    std::cin >> ile;

    p.resize(ile);

    int n = p.size();
    for (auto i = 1; i <= n; ++i) {
        p[i - 1] = i;
    }
    perm(n, p);
    return 0;
}