蓝桥杯基础知识2 全排列 next_permutation()， prev_permutation()

蓝桥杯基础知识2 全排列 next_permutation()， prev_permutation()

#include<bits/stdc++.h>
using namespace std;

int a[10];

int main(){
    for(int i = 1; i <= 4; ++i)a[i] = i;	//4*3*2*1 = 24
    
    bool tag = true;
    
    while(tag){
        for(int i=1; i <= 4; ++i)cout << a[i] << ' ';
        cout << '\n';
        tag = next_permutation(a + 1, a + 1 + 4);
    }
	return 0;
}

C++ 在线工具 | 菜鸟工具 (runoob.com)

#include<bits/stdc++.h>
using namespace std;

int a[10];

int main(){
    
    a[1] = 2, a[2] = 3, a[3] = 4, a[4] = 1;	//初始顺序为2341
    bool tag = true;
    
    while(tag){
        for(int i=1; i <= 4; ++i)cout << a[i] << ' ';
        cout << '\n';
        tag = next_permutation(a + 1, a + 1 + 4);
    }
	for(int i = 1; i <= 4; ++i)cout << a[i] << ' ';
	//从2开始进行全排列，输出最后一个排列4321后，顺序变为1234
	return 0;
}

next_permutation函数用于生成当前序列的下一个序列。按字典序对序列重新排列，如果存在下一个排序，则当前序列更改为下一个排序，并返回true；如果当前序列已经是最后一个排列，则将序列更改为第一个排列，并返回false。

next_permutation全排列函数的时间复杂度是O（n），其中n是序列的长度。next_permutation（）需要遍历和比较序列的每一个元素，以确定下一个排列组合。

#include<bits/stdc++.h>
using namespace std;

int a[10];

int main(){
    
    a[1] = 2, a[2] = 3, a[3] = 4, a[4] = 1;	//初始顺序为2341
    bool tag = true;
    
    while(tag){
        for(int i=1; i <= 4; ++i)cout << a[i] << ' ';
        cout << '\n';
        tag = prev_permutation(a + 1, a + 1 + 4);
    }
	for(int i = 1; i <= 4; ++i)cout << a[i] << ' ';
	//从2开始进行全排列，输出最后一个排列1234后，顺序变为4321
	return 0;
}

prev_permutation函数用于生成当前序列的上一个序列。按字典序对序列重新排列，如果存在上一个排序，则当前序列更改为上一个排序，并返回true；如果当前序列已经是第一个一个排列，则将序列更改为最后一个排列，并返回false。

prev_permutation函数时间复杂度为O（n），其中n是序列的长度。prev_permutation（）需要遍历和比较序列的每一个元素，以确定上一个排列组合。

reference:

https://wenku.csdn.net/answer/7mxkew7uyk#

STL中关于全排列next_permutation以及prev_permutation的用法 - Xenny - 博客园 (cnblogs.com)

STL next_permutation和prev_permutation 算法原理和自行实现_next_permutation实现思想-CSDN博客

STL中关于全排列next_permutation以及prev_permutation的用法 - Xenny - 博客园 (cnblogs.com)