Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 373|回复: 0

[默认分类] 全排列算法原理和实现

[复制链接]
  • TA的每日心情
    开心
    2021-12-13 21:45
  • 签到天数: 15 天

    [LV.4]偶尔看看III

    发表于 2018-7-11 14:36:56 | 显示全部楼层 |阅读模式
    本文为原创,如需转载,请注明作者和出处,谢谢!

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


    #include
    <
    stdio.h
    >
       


    int
      n
    =
      
    0
    ;  


    void
      swap(
    int
      
    *
    a,
    int
      
    *
    b)
    {     
       
    int
      m;     
        m
    =
      
    *
    a;     
       
    *
    a
    =
      
    *
    b;     
       
    *
    b
    =
      m;
    }  

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

    int
      main()
    {     
       
    int
      list[]
    =
      {
    1
    ,
    2
    ,
    3
    ,
    4
    ,
    5
    };     
        perm(list,
    0
    ,
    4
    );     
        printf(
    "
    total:%d\n
    "
    , n);     
       
    return
      
    0
    ;
    }  


    1. 谁有更高效的递归和非递归算法,请回贴。
    复制代码

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-29 13:54 , Processed in 0.441878 second(s), 37 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表