论如何秒杀一个可怜弱小无辜的全排列问题
2024-07-26 08:03:25
发布于：湖南
21阅读
0回复
0点赞
本知识点供存档用
首先，我们看一下长度为5的全排列：
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 2 4
1 3 5 4 2
...
在这些之中，我们找到一种排列：
4 2 5 3 1
你知道它下一个全排列是什么吗？
我们可以通过大脑一秒知道下一个是4 3 1 2 5.
怎么得来的呢？
我们发现只需要通过这4步：
1.从后往前，找到第一个前面的数小于后面的数，即2.
2.从后往前，找到第一个比当前数大的数.这个数是3.
3.交换这两个数.此时为4 3 5 2 1.
4.在3后面的数用升序排列（由于后面的数已是降序，可以使用反转节省时间）.此时为4 3 1 2 5.
通过这种办法，我们就能获取所有数下一个全排列.不信你去试试（
代码如下：
bool next_permunation(){//获取下一个排列
int i;
for(i = n; i > 1; i--){//第一步，找数
if(a[i] > a[i - 1]) break;
}
if(i == 1) return 0;//没找到就说明全排列结束了
for(int j = n; j >= i; j--){//第二步，可以二分优化，但没必要
if(a[j] > a[i - 1]){
swap(a[j], a[i - 1]);//第三步，交换
reverse(a + i, a + n + 1);//第四步，反转
return 1;
}
}
}
时间复杂度：.
有帮助，赞一个