UC知道全排列问题
来源：百度知道 编辑：UC知道 时间：2024/09/22 01:32:58
void Perm(T list[],int k,int m)
{
int i;
if(k==m){//输出一个排列方式
for(i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
else //有多个排列方式，递归产生
for(i=k;i<=m;i++){
Swap(list[k],list[i]);//用list[k]与list[k:m]中的每个元素进行交换
Perm(list,k+1,m);//产生list[k+1:m]的所有排列方式，并调用它作为list[0:k]的后缀
Swap(list[k],list[i]);//这句加了真是不懂！
}
}
template<class T>
inline void Swap(T& a,T& b)
{
T temp=a;
a=b;
b=temp;
}
谁解释下这算法
{
int i;
if(k==m){//输出一个排列方式
for(i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
else //有多个排列方式，递归产生
for(i=k;i<=m;i++){
Swap(list[k],list[i]);//用list[k]与list[k:m]中的每个元素进行交换
Perm(list,k+1,m);//产生list[k+1:m]的所有排列方式，并调用它作为list[0:k]的后缀
Swap(list[k],list[i]);//这句加了真是不懂！
}
}
template<class T>
inline void Swap(T& a,T& b)
{
T temp=a;
a=b;
b=temp;
}
谁解释下这算法
Swap(list[k],list[i]);//这句加了真是不懂！
前面不是改变了list吗？这里就还原 当前层的list。
比如 12345
改变一下 21345
显示 子排列
还原 12345
再改变 32145
。。。。
不然会有重复和漏选
如abc 的输出 |不加的话
| abc 11交换 22交换 |abc
| acb 23交换 | acb 因为没有还原
| bac 还原成abc然后21交换，22交换|cab 所以21交换变成了ca交换
| bca 23交换 | cba
| cba 还原成abc然后31交换，22交换|abc 31交换又是ac交换 重复
| cab 23交换 | acb !重复