c/c :全排列问题-尊龙官方平台

c/c :全排列问题

el/2024/3/25 17:04:54

c/c :全排列问题

啥叫全排列?

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。

当m=n时所有的排列情况叫全排列。

假设现在有三个数字:0 1 2,将其全排列结果为:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

我们有几种方式可以实现全排列。

最简单,最暴力的是枚举。

【例1】

#include 
#include void permutations()
{int i, j, k;for (i = 0; i < 3; i  )for (j = 0; j < 3; j  )for (k = 0; k < 3; k  ){if (i != j && i != k && j != k)printf("%d %d %d\n", i, j, k);}
}int main()
{permutations();return 0;
}

其实我们可以优化一点:

【例2】

#include 
#include void permutations()
{int i, j, k;for (i = 0; i < 3; i  ){for (j = 0; j < 3; j  ){if (i == j){continue;}for (k = 0; k < 3; k  ){if (i == k || j == k){continue;}printf("%d %d %d\n", i, j, k);}}}
}int main()
{permutations();return 0;
}

哈哈,只是换汤不换药,但是在嵌套循环很多的时候性能会有很大的提高,毕竟可以提前发现,少做很多的无用功。

另外一种可以使用mark标记数组,当需要全排列的数字很多时比较好用。

假设现在需要对0 1 2 3进行全排列:

【例3】

#include 
#include int permutations()
{int total = 0;int a[4];for (a[0] = 0; a[0] < 4; a[0]  )for (a[1] = 0; a[1] < 4; a[1]  )for (a[2] = 0; a[2] < 4; a[2]  )for (a[3] = 0; a[3] < 4; a[3]  ){int mark[4] = {0, 0, 0, 0};int i;for (i = 0; i < 4; i  ){mark[a[i]]  ;}int sum = 0;for (i = 0; i < 4; i  ){if (mark[i]){sum  ;}}if (sum == 4){printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);total   ;}}return total;
}int main()
{int result = permutations();printf("result is %d\n", result);return 0;
}
[test1280@localhost ~]$ !g
gcc -o main main.c
[test1280@localhost ~]$ ./main
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
……

上述方法其实也是枚举,虽然能在数字多时看起来简洁,但是个人认为,性能上还不如第二种方法,毕竟第二种可以减少很多不必要的循环,可以预先检查。

总结上面三点,都是枚举,都很暴力。

有没有更好一点的方法?

我们可以使用dfs来对全排列进行计算。

【例4】

#include 
#include /****************************************************** 函数名称:dfs* 参数列表:mark-标记数组;step-当前为第几步;all-一共有多少步;path-踪迹数组* 函数描述:深度优先,遍历step步时可能的情况总数* 返回值  :step步可能出现的情况总数* 备注    :* author  :test1280* history :2017/05/14* ***************************************************/
int dfs(int *mark, int step, int all, int *path)
{if (step == all){int i;for (i = 0; i < all; i  ){printf("%d ", path[i]);}printf("\n");return 1;}int i;int total = 0;for (i = 0; i <= all; i  ){if (mark[i]){continue;}mark[i] = 1;path[step] = i;total = total   dfs(mark, step   1, all, path);mark[i] = 0;}return total;
}/******************************************************** 函数名称:permutations* 参数列表:all-共有all个数进行全排列* 函数描述:全排列all个数字,从0到all-1* 返回值  :全排列all个数字的情况总数* 备注    :* author  :test1280* history :2017/05/14* ***************************************************/
int permutations(int all)
{int *mark = (int *)malloc(sizeof(int) * all);int *path = (int *)malloc(sizeof(int) * all);int total = 0;int i;for (i = 0; i < all; i  ){mark[i] = 0;}for (i = 0; i < all; i  ){mark[i] = 1;// now-step is 0path[0] = i;total = total   dfs(mark, 1, all, path);mark[i] = 0;}return total;
}int main()
{int all = 10;int result = permutations(all);printf("%d\n", result);return 0;
}

输出可能会有一会~

我们将那些输出都干掉,只是求结果总数:

【例5】

#include 
#include /****************************************************** 函数名称:dfs* 参数列表:mark-标记数组;step-当前为第几步;all-一共有多少步;* 函数描述:深度优先,遍历step步时可能的情况总数* 返回值  :step步可能出现的情况总数* 备注    :* author  :test1280* history :2017/05/14* ***************************************************/
int dfs(int *mark, int step, int all)
{if (step == all){return 1;}int i;int total = 0;for (i = 0; i <= all; i  ){if (mark[i]){continue;}mark[i] = 1;total = total   dfs(mark, step   1, all);mark[i] = 0;}return total;
}/******************************************************** 函数名称:permutations* 参数列表:all-共有all个数进行全排列* 函数描述:全排列all个数字,从0到all-1* 返回值  :全排列all个数字的情况总数* 备注    :* author  :test1280* history :2017/05/14* ***************************************************/
int permutations(int all)
{int *mark = (int *)malloc(sizeof(int) * all);int total = 0;int i;for (i = 0; i < all; i  ){mark[i] = 0;}for (i = 0; i < all; i  ){mark[i] = 1;// now-step is 0total = total   dfs(mark, 1, all);mark[i] = 0;}return total;
}int main()
{int all = 10;int result = permutations(all);printf("%d\n", result);return 0;
}

输出如下:

[test1280@localhost ~]$ !g
gcc -o main main.c
[test1280@localhost ~]$ ./main 
3628800

注意一点,dfs在这里面,总是递归调用,从全局程序运行生长来看,他做的也是对all个数,用了all次循环,区别在于,其将【例2】中的预先判断做了极大的发挥,使其结合mark标记数组,再加上递归的特性,使得性能大大增加。

大家不妨将【例3】改为10个数字的全排列,只输出结果,然后和【例4】进行性能比较。

有没有别的方法呢?


http://www.ngui.cc/el/5127163.html

相关文章

杭电-pid1181-变形课

杭电-pid1181-变形课 problem description 呃......变形课上harry碰到了一点小麻烦,因为他并不像hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使a物体变成b物…

杭电-pid1008-elevator

杭电-pid1008-elevator 好吧,其实这道题是水过去的。。 problem description the highest building in our city has only one elevator. a request list is made up with n positive numbers. the numbers denote at which floors the elevator will stop, in s…

杭电-pid1012-u calculate e

杭电-pid1012-u calculate e #include #include int main() {printf("n e\n- -----------\n0 1\n1 2\n2 2.5\n");double num 2.5;double base 2;int i 3;while (i < 10){base base * i;num num 1 / base;printf("%d %…

杭电-pid1013-digital roots

杭电-pid1013-digital roots 九余数定理 #include using namespace std;int main() {string s;while (cin>>s){if (s[0] 0){break;}int sum 0, i;for (i 0; i < s.length(); i){sum sum s[i] - 0;}if (sum % 9 0){cout<<"9"<…

linux:curl的使用

linux:curl的使用 curl is a tool to transfer data from or to a server, using one of the supported protocols (http, https, ftp, ftps, tftp, dict, telnet, ldap or file). the command is designed to work without user interaction. curl支持多种协…

c/c :类型转换

c:dynamic_cast、static_cast 实验环境: [test1280localhost ~]$ uname -a linux localhost.localdomain 2.6.18-371.el5 #1 smp thu sep 5 21:21:44 edt 2013 x86_64 x86_64 x86_64 gnu/linux …… gcc 版本 4.1.2 20080704 (red hat 4.1.2-54) c/c中…

lua:ipairs/pairs

lua:ipairs/pairs lua中有两个很类似的函数:ipairs以及pairs。 实验环境: [test1280localhost 20170531]$ uname -a linux localhost.localdomain 2.6.18-371.el5 #1 smp thu sep 5 21:21:44 edt 2013 x86_64 x86_64 x86_64 gnu/linux [te…

常用linux命令:ssh

常用linux命令:ssh 以后随时记录一些工作中用到的命令,这些命令是常用的,但是参数可能比较多,容易混淆,不是很容易记住;也有可能某天忽然间需要用了,还要man一下就… 总之吧,这里讲…

常用linux命令:scp

常用linux命令:scp 传输文件,由本机传输至远端: scp -oport19222 /home/test1280/test.json test128010.1.70.206:/home/test1280 scp -oport19222 test.json test128010.1.70.206:/home/test1280scp -oportport localpath usernameip:desta…

常用linux命令:grep

常用linux命令:grep 1.搜索当前目录下关键字 [test1280localhost log]$ grep -nr "*" ./* ./ismpbus.log:18:2017/05/22 09:13:11.284 info - * open a subserver socket from 127.0.0.1,m_sockfd8,port12600. ./ismpbus.log:25:2017/05/22 09:13:11.28…
网站地图