# 14183: 【原4183】全排列

### 题目描述

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

## 样例输入

``````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
``````

## 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;
}
``````