#pragma once

#include <vector>

std::vector<int> NextPermutation(std::vector<int> permutation, size_t len) {
    size_t k = len - 2;
    while (permutation[k] > permutation[k + 1]) {
        --k;
    }
    size_t t = k + 1;
    while (t < len - 1 && permutation[t + 1] > permutation[k]) {
        ++t;
    }
    int temp = permutation[k];
    permutation[k] = permutation[t];
    permutation[t] = temp;
    while (k + 1 < len - 1) {
        temp = permutation[k + 1];
        permutation[k + 1] = permutation[len - 1];
        permutation[len - 1] = temp;
        ++k;
        --len;
    }
    return permutation;
}

std::vector<std::vector<int>> GeneratePermutations(size_t len) {
    if (len == 1) {
        return {{0}};
    }
    std::vector<std::vector<int>> permutations;
    std::vector<int> permutation, last_permutation, next_permutation;
    for (size_t i = 0; i < len; ++i) {
        permutation.push_back(static_cast<int>(i));
        last_permutation.push_back(static_cast<int>(len - i - 1));
    }
    permutations.push_back(permutation);
    do {
        permutation = NextPermutation(permutation, len);
        permutations.push_back(permutation);
    } while (permutation != last_permutation);
    return permutations;
}