C语言实现全排列算法模板的方法

2023-08-02 13:13:06 79

程序的主要思路是：

1.把第1个数换到最前面来（本来就在最前面），准备打印1xx，再对后两个数2和3做全排列。

2.把第2个数换到最前面来，准备打印2xx，再对后两个数1和3做全排列。

3.把第3个数换到最前面来，准备打印3xx，再对后两个数1和2做全排列。

可见这是一个递归的过程，把对整个序列做全排列的问题归结为对它的子序列做全排列的问题，注意我没有描述BaseCase怎么处理，你需要自己想。你的程序要具有通用性，如果改变了N和数组a的定义（比如改成4个数的数组），其它代码不需要修改就可以做4个数的全排列（共24种排列）。

解题过程：

1.当N=1的时候，则直接打印数列即可。

2.当N=2的时候，设数组为[a,b]

打印a[0],a[1]（即a，b）

交换a[0],a[1]里面的内容

打印a[0],a[1] （此时已变成了[b,a]）

3.当N=3的时候，数组为[a,b,c]

3.1把a放在a[0]的位置（原本也是如此，a[0]=a[0]），打印b,c的全排列（即a[1],a[2]的全排列）

3.2把b放在a[0]的位置（这时候需要交换原数组的a[0]和a[1]），然后打印a,c的全排列，打印完后再换回原来的位置，即a还是恢复到a[0]，b还恢复到a[1]的位置

3.3把c放在a[0]的位置（这时候需要交换的是原数组的a[0]和a[2]），然后打印a,b的全排列，打印完后再换回原来的位置，即a还是恢复到a[0]，b还恢复到a[1]的位置

至此，全排列完成

当N=4，5，6,……的时候，以此类推。

#include

/************************************************************************/
/*功能：实现两个整形参数值交换
/*参数：
/*lhs--int类型的指针，指向待交换数1的地址
/*rhs--int类型的指针，指向待交换数2的地址
/************************************************************************/
voidSwap(int*lhs,int*rhs)
{
intt=*lhs;

*lhs=*rhs;
*rhs=t;
}

/************************************************************************/
/*功能：实现全排列功能
/*参数：
/*source--整数数组，存放需要全排列的元素
/*begin--查找一个排列的开始位置
/*end--查找一个排列的结束位置，当begin=end时，表明完成一个排列
/************************************************************************/
voidFullPermutation(intsource[],intbegin,intend)
{
inti;

if(begin>=end)//找到一个排列
{
for(i=0;i
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C语言实现全排列算法模板的方法

热门推荐

随机推荐