14183: 【原4183】全排列

题目

题目描述

author: Yifan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4183

题目描述

给出正整数n，1到n这n个数可以构成n!中排列，将这些排列按从小到大的顺序列出。如n = 3时，依次列出12 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1这六个排列。

现在给出某个排列，求出这个排列的下k个排列。n ... 3 2 1下1个排列是第1个排列1 2 3 ... n。例如在n = 3, k = 2时给出排列2 3 1，它的下1个排列是3 1 2，下2个排列是3 2 1，所以答案是3 2 1。

本题禁止使用std::next_permutation。

输入格式

第一行是一个正整数m，表示m组测试数据。接下来每组测试数据第一行是2个正整数n和k，第二行是n个正整数，表示1到n的一个排列。

输出格式

对于每组输入数据，输出一行, n个数，中间用空格隔开，表示输入排列的下k个排列。

样例输入

3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10

样例输出

3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10

数据规模

对于30%的数据，\(1 \le n \le 6, k = 1, m = 1\)。

对于60%的数据，\(1 \le n \le 6, 1 \le k \le 10\)。

对于100%的数据，\(1 \le n \le 1000, 1 \le k \le 50, 1 \le m \le 10\)。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/18.
//
// 全排列

#include <iostream>
#include <algorithm>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

template<typename _BidirectionalIterator, typename _Compare>
bool
aVeryStrangeFunction(_BidirectionalIterator __first,
                     _BidirectionalIterator __last, _Compare __comp) {
    if (__first == __last)
        return false;
    _BidirectionalIterator __i = __first;
    ++__i;
    if (__i == __last)
        return false;
    __i = __last;
    --__i;

    for (;;) {
        _BidirectionalIterator __ii = __i;
        --__i;
        if (__comp(__i, __ii)) {
            _BidirectionalIterator __j = __last;
            while (!__comp(__i, --__j)) {}
            std::iter_swap(__i, __j);
            std::__reverse(__ii, __last,
                           std::__iterator_category(__first));
            return true;
        }
        if (__i == __first) {
            std::__reverse(__first, __last,
                           std::__iterator_category(__first));
            return false;
        }
    }
}

int main() {
    int M;
    cin >> M;
    while (M--) {
        int n, k;
        cin >> n >> k;
        auto array = new int[n];
        for (int i = 0; i < n; ++i) {
            cin >> array[i];
        }
        while (k--) {
            aVeryStrangeFunction(array, array + n, __gnu_cxx::__ops::__iter_less_iter());
        }
        for (int j = 0; j < n; ++j) {
            cout << array[j] << ' ';
        }
        cout << endl;
        delete[] array;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

void reverse_nums(int* from, int* end) {
    for (auto p = from, q = end - 1; p < q; ++p, --q) {
        auto temp = *p;
        *p = *q;
        *q = temp;
    }
}

void permutation_step(int* from, int* end) {
    //寻找逆序数
    auto p = end - 2;
    for (; p >= from && *p >= * (p + 1); --p);
    //判断是否完成
    if (p < from) {
        reverse_nums(from, end);
        return;
    }
    auto q = end - 1;
    for (; *p > * q; --q);
    //交换
    auto temp = *p;
    *p = *q;
    *q = temp;
    reverse_nums(p + 1, end);
}

int main() {
    int m;
    scanf("%d", &m);

    for (; m > 0; --m) {
        int a[1009] = { 0 };
        int n, k;
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        for (int i = 0; i < k; ++i)
            permutation_step(a, a + n);
        printf("%d", a[0]);
        for (int i = 1; i < n; ++i)
            printf(" %d", a[i]);
        printf("\n");
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <algorithm>
using namespace std;

int D[1000];
void run() {
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> D[i];
    if (N != 1) {
        if (N == 2) {
            for (int t = 0; t < K; t++) swap (D[0], D[1]);
        } else {
            for (int t = 0; t < K; t++) {
                int r = N - 2;
                while (r >= 0 && D[r] >= D[r + 1]) --r;
                if (r >= 0) {
                    int l = N - 1;
                    while (D[r] >= D[l]) --l;
                    swap(D[r], D[l]);
                }
                reverse(D + r + 1, D + N);
            }
        }
    }
    for (int i = 0; i < N; i++) cout << D[i] << " ";
    cout << endl;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) run();
    return 0;
}