全排列算法一个C语言全排列的算法。 比如,输入3,则将123的全排列全部输出:123,132,213,231
全排列算法 时间:2021-08-31 阅读:(
)
全排列的公式
全排列数f(n)=n!(定义0!=1) 1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
这是由于算法只是考虑到了如何输出全排列,而没有考虑到换位是否有问题。
所以我提出了解决方案,就是换位函数修改下
如 1 2 3 换位的话 ,不应该直接 3 2 1这样 ,
让3和1直接换位; 而是让3排在最前后 ,1 2 依次向后 以下介绍全排列算法四种:
(A)字典序法
(B)递增进位制数法
(C)递减进位制数法
(D)邻位对换法 对给定的字符集中的字符规定了一个先后关系,在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。
[例]字符集{1,2,3},较小的数字较先,
这样按字典序生成的全排列是:123,132,213,231,312,321。
[注意] 一个全排列可看做一个字符串,字符串可有前缀、后缀。
1)生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有其他的。
这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。
[例]839647521是1--9的排列。
1—9的排列最前面的是123456789,最后面的是987654321,从右向左扫描若都是增的,就到987654321,也就没有下一个了。
否则找出第一次出现下降的位置。
1)由排列求中介数 在字典序法中,中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。
在递增进位制数法中,中介数的各位是由排列中的数字决定的。
即中介数中各位的下标与排列中的数字(2—n)一致。
可看出n-1位的进位链。
右端位逢2进1,右起第2位逢3进1,…,
右起第i位逢i+1进1,i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。
上面是由中介数求排列。
由序号(十进制数)求中介数(递增进位制数)如下:
m=m1,0≤m≤n!-1
m1=2m2+kn-1,0≤kn-1≤1
m2=3m3+kn-2,0≤kn-2≤2
……………
mn-2=(n-1)mn-1+k2,0≤k2≤n-2
mn-1=k1,0≤k1≤n-1
p1p2…pn←→(k1k2…kn-1)↑←→m
在字典序法中由中介数求排列比较麻烦,我们可以通过另外定义递增进位制数加以改进。
为方便起见,令ai+1=kn-1,i=1,2,…,n-1
(k1k2…kn-1)↑=(anan-1…a2)↑
ai:i的右边比i小的数字的个数
在这样的定义下,
有839647521←→(67342221)↑
(67342221)↑+1=(67342300)↑←→849617523
6×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1 =279905
由(anan-1…a2)↑求p1p2…pn。
从大到小求出n,n-1,…,2,1的位置
_ ... _ n _ _ …_ (an个空格)
n的右边有an个空格。
n-1的右边有an-1个空格。
…………
2的右边有a2个空格。
最后一个空格就是1的位置。
在递增进位制数法中,中介数的最低位是逢2进1,进位频繁,这是一个缺点。
把递增进位制数翻转,就得到递减进位制数。
(anan-1…a2)↑→(a2a3…an-1an)↓
839647521→ (12224376)↓
(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989
[注意]求下一个排列十分容易 递减进位制数法的中介数进位不频繁,求下一个排列在不进位的情况下很容易。
这就启发我们,能不能设计一种算法,下一个排列总是上一个排列某相邻两位对换得到的。
递减进位制数字的换位是单向的,从右向左,而邻位对换法的换位是双向的。
这个算法可描述如下:
对1—n-1的每一个偶排列,n从右到左插入n个空档(包括两端),生成1—n的n个排列。
对1—n-1的每一个奇排列,n从左到右插入n个空档,生成1—n的n个排列。
对[2,n]的每个数字都是如此。
839647521
字典序法 递增进位制法 递减进位制法 邻位对换法
下一个 839651247 849617523 893647521 836947521
中介数 72642321↑ 67342221↑ 12224376↓ 10121372↓
序 号 297191 279905 340989 203393求高手解答本“实现数组全排列”的算法思想的详细思路。
如果排列因子数量很少, 可以用2进制位来表示。
如:["a", "b", "c", "d", "e"] 可以按位表示
0 0 0 0 0
相应位为1时表示, 使用该因子。
一个C语言全排列的算法。 比如,输入3,则将123的全排列全部输出:123,132,213,231
#include
main()
{
int a1,a2,a3,a4,a5,a6,a7,a8,a9,n,t=0;
scanf("%d",&n);
for(a1=1;a1<=n;a1++)
if(n==1){printf("%d
",a1);t=t+1;}
else
for (a2=1;a2<=n;a2++)
if(a2!=a1)
{if(n==2) {printf("%d%d
",a1,a2);t=t+1;}
else
for (a3=1;a3<=n;a3++)
if(a3!=a2&&a3!=a1)
{if(n==3) {printf("%d%d%d
",a1,a2,a3);t=t+1;}
else
for (a4=1;a4<=n;a4++)
if(a4!=a3&&a4!=a2&&a4!=a1)
{if(n==4) {printf("%d%d%d%d
",a1,a2,a3,a4);t=t+1;}
else
for (a5=1;a5<=n;a5++)
if(a5!=a4&&a5!=a3&&a5!=a2&&a5!=a1)
{if(n==5) {printf("%d%d%d%d%d
",a1,a2,a3,a4,a5);t=t+1;}
else
for (a6=1;a6<=n;a6++)
if(a6!=a5&&a6!=a4&&a6!=a3&&a6!=a2&&a6!=a1)
{if(n==6) {printf("%d%d%d%d%d%d
",a1,a2,a3,a4,a5,a6);t=t+1;}
else
for (a7=1;a7<=n;a7++)
if(a7!=a6&&a7!=a5&&a7!=a4&&a7!=a3&&a7!=a2&&a7!=a1)
{if(n==7) {printf("%d%d%d%d%d%d%d
",a1,a2,a3,a4,a5,a6,a7);t=t+1;}
else
for (a8=1;a8<=n;a8++)
if(a8!=a7&&a8!=a6&&a8!=a5&&a8!=a4&&a8!=a3&&a8!=a2&&a8!=a1)
{if(n==8) {printf("%d%d%d%d%d%d%d%d
",a1,a2,a3,a4,a5,a6,a7,a8);t=t+1;}
else
for (a9=1;a9<=n;a9++)
if(a9!=a8&&a9!=a7&&a9!=a6&&a9!=a5&&a9!=a4&&a9!=a3&&a9!=a2&&a9!=a1)
{if(n==9) {printf("%d%d%d%d%d%d%d%d%d
",a1,a2,a3,a4,a5,a6,a7,a8,a9);t=t+1;}
}
}
}
}
}
}
}
}
printf("共有%d种
",t);
getchar();getchar();
}
自己辛辛苦苦写的,用dev c运行成功
LayerStack(成立于2017年),当前正在9折促销旗下的云服务器,LayerStack的云服务器采用第 3 代 AMD EPYC™ (霄龙) 处理器,DDR4内存和企业级 PCIe Gen 4 NVMe SSD。数据中心可选中国香港、日本、新加坡和洛杉矶!其中中国香港、日本和新加坡分为国际线路和CN2线路,如果选择CN2线路,价格每月要+3.2美元,付款支持paypal,支付宝,信用卡等!...
ZJI又上新了!商家是原Wordpress圈知名主机商:维翔主机,成立于2011年,2018年9月启用新域名ZJI,提供中国香港、台湾、日本、美国独立服务器(自营/数据中心直营)租用及VDS、虚拟主机空间、域名注册等业务。本次商家新上韩国BGP+CN2线路服务器,国内三网访问速度优秀,适用8折优惠码,优惠后韩国服务器最低每月440元起。韩国一型CPU:Intel 2×E5-2620 十二核二十四线...
香港ctg云服务器香港ctg云服务器官网链接 点击进入妮妮云官网优惠活动 香港CTG云服务器地区CPU内存硬盘带宽IP价格购买地址香港1核1G20G3M5个19元/月点击购买香港2核2G30G5M10个40元/月点击购买香港2核2G40G5M20个450元/月点击购买香港4核4G50G6M30个80元/月点击购买香...
全排列算法为你推荐
权限表帮忙设计个用户权限表色空间XYZ的颜色空间封包是什么洛克王国封包是什么意思最好的电脑操作系统主流的电脑操作系统都有哪些?照片ps是什么意思PS照片是什么意思?锤子手机发布会视频我如果学习好会遇见长的漂亮而且优秀的人吗?如果我学习好,长的漂亮的人会对我有好感吗?人工电源网络设备EMC试验等级怎么选择?有选择标准吗?是什么标准?谢谢!人工电源网络EMC测试的介绍怎样下载文件百度云网盘只有提取码怎么下文件云电视是什么意思4K2K是什么意思?
深圳主机租用 中国万网虚拟主机 赵容 韩国俄罗斯 ix主机 美国仿牌空间 42u标准机柜尺寸 美国php主机 patcha gg广告 上海服务器 备案空间 沈阳主机托管 免费asp空间 美国盐湖城 工信部icp备案查询 后门 石家庄服务器 脚本大全 phpwind论坛 更多