全排列算法原理和实现-阿里云开发者社区

开发者社区> geekori> 正文

全排列算法原理和实现

简介: 本文为原创,如需转载,请注明作者和出处,谢谢! 全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3, 4, 5}为 例说明如何编写全排列的递归算法。
+关注继续查看
本文为原创,如需转载,请注明作者和出处,谢谢!

全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3, 4, 5}为

例说明如何编写全排列的递归算法。
1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身,从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
从而可以推断,设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p),pn = p - {rn}。
因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。当n = 1时perm(p} = r1。
为了更容易理解,将整组数中的所有的数分别与第一个数交换,这样就总是在处理后n-1个数的全排列。
算法如下:

#include <stdio.h>  

int n = 0;  

void swap(int *a, int *b) 
{     
    
int m;     
    m 
= *a;     
    
*= *b;     
    
*= m; 
}  
void perm(int list[], int k, int m) 
{     
    
int i;     
    
if(k > m)     
    {          
        
for(i = 0; i <= m; i++)             
            printf(
"%d ", list[i]);         
        printf(
"/n");         
        n
++;     
    }     
    
else     
    {         
        
for(i = k; i <= m; i++)         
        {             
            swap(
&list[k], &list[i]);             
            perm(list, k 
+ 1, m);             
            swap(
&list[k], &list[i]);         
        }     
    } 

int main() 
{     
    
int list[] = {12345};     
    perm(list, 
04);     
    printf(
"total:%d/n", n);     
    
return 0

谁有更高效的递归和非递归算法,请回贴。


国内最棒的Google Android技术社区(eoeandroid),欢迎访问!

《银河系列原创教程》发布

《Java Web开发速学宝典》出版,欢迎定购

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
How to post a Java object to http end point which accepts json string
How to post a Java object to http end point which accepts json string
4 0
SpringCloud database connection debug
SpringCloud database connection debug
3 0
set Spring log level to debug so that we can learn more from log
set Spring log level to debug so that we can learn more from log
3 0
29行代码使用HTML5 Canvas API绘制一颗红心
29行代码使用HTML5 Canvas API绘制一颗红心
1 0
Spark平台上提交作业到集群生成的日志文件
Spark平台上提交作业到集群生成的日志文件
3 0
Eclipse/NSight: methond could not resolved
Eclipse/NSight: methond could not resolved
3 0
注解@notBlank的工作原理
注解@notBlank的工作原理
4 0
Spark集群的启动日志
Spark集群的启动日志
3 0
JSP页面和产品明细页面的绑定关系在Hybris WCMS cockpit什么地方能够找到
JSP页面和产品明细页面的绑定关系在Hybris WCMS cockpit什么地方能够找到
1 0
Spring里Bean类的运行时小写之谜
Spring里Bean类的运行时小写之谜
3 0
+关注
geekori
欧瑞科技创始人&amp;CEO,东北大学计算机专业硕士,拥有超过20年软件开分经验。欧瑞学院金牌讲师、51CTO学院金牌讲师、CSDN学院特约讲师、畅销书作者,企业内训讲师。曾出版过超过30本IT畅销书,涉猎移动开发、跨平台开发、机器学习、区块链、大数据、编译器等领域。
419
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载