关于全排列算法（支持有重复的数字的情况）
对于求一个全排列的问题，我们不可能一下子列出所有排列的情况（n！种情况），
我们可以从一个已知的排列，来获得下一个排列。对于任意的一个排列，他的下一个排列是什么了？
比如说：453987621，我的想法是：
从该排列的右边向左边遍历，找到第一个比其右边小的数，此处是
3（3<9），然后遍历3右边的数字，找到比他大的最小的数字，此处为6，
将3与6交换，排列变为456987321，最后将6
后面的数字逆序即可，（987321变成123789），所以得到的下一个
排列为456123789。
开始时我们初始化为123456789，最后判断得到987654321的排列，则得到了所有的全排列。
代码如下：
文章图片
#include
<
iostream
>
文章图片
using namespace
std;
文章图片
void
init(
int *
a,
int
n);
文章图片
void
_swap(
int &
i,
int &
j);
文章图片
void
inverse(
int *
a,
int
startpos,
int
n);
文章图片
int
main(
int
)
文章图片
文章图片
...
{
文章图片
文章图片
int a[100] = ...{0};
文章图片
int n,i,j,k;
文章图片
cout << "请输入全排列的个数(n < 10)" << endl;
文章图片
cin >> n;
文章图片
init(a,n);
//初始化为类似于1234...的排列
文章图片
文章图片
while(1)...{
文章图片
for(i = n - 1;
i >= 1;
i--)
文章图片
文章图片
...{
文章图片
if(a[i] < a[i + 1])
文章图片
文章图片
...{
文章图片
break;
文章图片
}
文章图片
}
文章图片
if(i < 1)
文章图片
文章图片
...{
文章图片
break;
//已经遍历完毕了
文章图片
}
文章图片
else
文章图片
文章图片
...{
文章图片
for(j = i + 1;
j <= n;
j++)
文章图片
文章图片
...{
文章图片
if(a[i] >= a[j])//若是1234的情况，j最终为n+1，仍然正确
文章图片
文章图片
...{
文章图片
break;
//加上"="后则可以解决重复数字排列的问题，如对1134进行的全排列
文章图片
}
文章图片
}
文章图片
_swap(a[i],a[j - 1]);
文章图片
inverse(a,i + 1,n);
文章图片
for(i = 1;
i <= n;
i++)
文章图片
文章图片
...{
文章图片
cout << a[i];
文章图片
}
文章图片
cout << endl;
文章图片
}
文章图片
}
文章图片
return -1;
文章图片
}
文章图片
void
_swap(
int &
i,
int &
j)
文章图片
文章图片
...
{
文章图片
int temp;
文章图片
temp = i;
文章图片
i = j;
文章图片
j = temp;
文章图片
}
文章图片
void
init(
int *
a,
int
n)
文章图片
文章图片
...
{
文章图片
int i;
文章图片
for(i = 1;
i <= n;
i++)
文章图片
文章图片
...{
文章图片
a[i] = i;
文章图片
a[1] =1;
文章图片
a[2] = 1;
文章图片
cout << a[i];
文章图片
}
文章图片
cout << endl;
文章图片
}
文章图片
void
inverse(
int *
a,
int
startpos,
int
n)
文章图片
文章图片
...
{
文章图片
int i,mid = (n - startpos+ 1) / 2 ;
文章图片
for(i = 0;
i < mid;
i++)
文章图片
文章图片
...{
文章图片
_swap(a[startpos + i],a[n - i]);
文章图片
}
文章图片
} 【关于全排列算法（支持有重复的数字的情况）】
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- 危险也是机会
- 四首关于旅行记忆的外文歌曲
- 活着就是生命的全部意义
- 醒不来的梦
- 一个健康的APP和健全的人格大体类似
- NeuVector 会是下一个爆款云原生安全神器吗（）
- 全过程工程咨询——时间管理（12）
- 关于自我为中心的一点感想
- 别墅庭院设计，不同的别墅庭院设计也给人视觉上完全不一样的！