作者:李宁,http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
全排列是将一组数按一定顺序进行排列,如果这组数有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;
*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[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;
}
谁有更高效的递归和非递归算法,请回贴。
分享到:
相关推荐
自己写的基于字符的全排列算法,代码简洁,高效,7位数的全排列都是秒排!用到了广度优先排列,深度优先搜索和几个递归,唯一没完成的是退出时释放内存,呵呵,破解密码时超有用的哟,,
全排列算法广泛应用于程序设计中,尤其是在需要穷举所有可能性的场合,比如组合数学、游戏设计、密码学等领域。 在C或C++中实现全排列算法,主要的思想是递归。基本步骤是首先固定第一个元素,然后对剩余的n-1个...
全排列算法是计算机科学中一个基础且重要的问题,它涉及到数组或序列的所有可能的线性排列方式。在处理这个问题时,我们通常会采用递归或迭代的方式来实现。下面将详细介绍全排列算法及其优化方法。 全排列算法的...
### 全排列算法解析 #### 1. 全排列的定义和公式 全排列是指从一个包含`n`个不同元素的集合中选取全部`n`个元素,并按一定顺序排列形成的不同序列总数。数学上,`n`个不同元素的全排列数记为`n!`(`n`的阶乘),即...
全排列算法: 比如字符串abc,全排列结果为abc,acb,bac,bca,cba,cab。
全排列算法是计算机科学中的一种基础算法,它用于找出给定集合的所有可能的排列组合。在本例中,我们将讨论如何使用递归方法实现全排列,以Java、C#、C++等主流编程语言为例。 全排列算法的核心思想是通过递归地...
全排列算法是计算机科学中一个基础且重要的概念,特别是在算法设计和分析中。它涉及到将一个给定的有限序列的所有可能的元素排列情况进行列举。在C#编程语言中,实现全排列算法可以帮助开发者解决多种问题,例如组合...
全排列算法是计算机科学中一个基础且重要的概念,主要用于生成一组数据的所有可能的排列组合。在实际应用中,它常用于解决各种优化问题、搜索问题和组合数学问题。本实例将详细阐述一种实现n个数全排列的算法。 ...
根据提供的信息来看,实际文章内容并未直接包含关于组合数学中的全排列算法的详细解析,而是主要介绍了清华大学计算机科学与技术系的一些活动与新生入学情况。不过,既然题目要求围绕组合数学中的全排列算法进行展开...
实现全排列组合的算法,供大家学习与参考。在需要对排列组合做差异分析的时候可以直接使用。例如:几个正则式的不同排列组合对匹配效果的影响
全排列算法是计算机科学中一个基础且重要的概念,特别是在算法设计和组合数学中。全排列是指从n个不同元素中取出m个元素,按照一定的顺序排列的所有可能的组合方式。在本例中,我们讨论的是使用C语言实现的全排列...
在处理某些问题时,如生成所有可能的组合或者解决排列组合问题,全排列算法是必不可少的工具。全排列指的是从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排列起来,所有的排列情况就构成了全排列。 ...
### Python字符串的全排列算法实例详解 #### 一、引言 在计算机科学中,全排列问题是一个常见的问题,尤其在解决密码学、组合优化等领域时尤为重要。全排列指的是从给定的一些元素中取出全部元素进行排列的方式。...
实现了字典序法、递增进位制数法、递减进位制数法、邻位对换法四种全排列算法。全排列算法有很多种,这里只是其中的一些,可以调试运行比较一下各种算法的效率。(该代码为初级版本,注重算法的实现,在交互方面需要...
利用中介数实现全排列算法,采用java实现。
全排列算法设计分析主要关注如何生成一个序列中所有可能的不同排列。全排列是指从n个不同元素中取出m个元素,按照一定的顺序排列起来,所有可能的排列方式组成的集合。这里我们将通过递归和迭代的方式来解析这个过程...
全排列算法是计算机科学中的一种基础算法,它用于找出一个给定序列的所有可能排列组合。在本案例中,我们关注的是使用JavaScript实现全排列的方法,包括回溯法和交换法。这两种方法都是解决全排列问题的有效策略,...