全排列算法原理和实现

简介: 本文为原创,如需转载,请注明作者和出处,谢谢! 全排列是将一组数按一定顺序进行排列,如果这组数有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[]  =  { 1 2 3 4 5 };     
    perm(list, 
0 4 );     
    printf(
" total:%d/n " , n);     
    
return   0

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


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

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

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

目录
相关文章
|
2月前
|
算法 C++ 索引
【算法】——全排列算法讲解
【算法】——全排列算法讲解
|
2月前
|
机器学习/深度学习 存储 算法
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
66 0
|
26天前
【洛谷 P1873】[COCI 2011_2012 #5] EKO _ 砍树 题解(向量+二分查找)
【COCI 2011/2012 #5】EKO 砍树问题摘要: - 伐木工Mirko需砍$M$米木材,只能砍一排树,使用二分搜索策略确定锯片最大高度$H$。 - 锯片设为$H$米时,会砍掉所有高于$H$的树顶,求得所需木材至少$M$米的最高$H$。 - 输入:树的数量$N$和所需木材总长$M$,每棵树的高度。 - 输出:锯片的最大高度。
8 0
|
2月前
|
算法
算法思想总结:前缀和算法
算法思想总结:前缀和算法
|
7月前
|
Java C++ Python
分治策略之最大子数组(Python实现)
分治策略之最大子数组(Python实现)
51 0
|
11月前
|
机器学习/深度学习 存储 算法
算法训练Day29|* 491.递增子序列* 46.全排列* 47.全排列 II
算法训练Day29|* 491.递增子序列* 46.全排列* 47.全排列 II
【算法】Leetcode算法题-求两数之和
【算法】Leetcode算法题-求两数之和
【算法】Leetcode算法题-求两数之和
|
自然语言处理 算法
经典算法之——解决全排列问题以及详解
经典算法之——解决全排列问题以及详解
202 0
|
算法 Java Linux
【基础算法】二分例题(我在哪?)
【基础算法】二分例题(我在哪?)
101 0
【基础算法】二分例题(我在哪?)
|
算法 Serverless 索引
二分算法-LeetCode 69
二分算法-LeetCode 69
78 0
二分算法-LeetCode 69