全排列算法的原理和实现代码

全排列是将一组数按一定顺序进行排列，如果这组数有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;
}

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

赞 (0)

相关推荐

  • C#算法之全排列递归算法实例讲解

    C#算法之全排列递归算法实例讲解

    排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列: 全排列:当n==m时,称为全排列: 比如:集合{ 1,2,3}的全排列为: 复制代码 代码如下: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 我们可以将这个排列问题画成图形表示,即排列枚举树,比如下图为{1,2,3}的排列枚举树,此树和我们这里介绍的算法完全一致: 算法思路: (1)n个元素的全排列=(n-1个元素的全排列)+(另一个元素作为前缀): (

  • 全排列算法-递归与字典序的实现方法(Java)

    全排列算法-递归与字典序的实现方法(Java)

    全排列算法-递归与字典序的实现方法(Java) 全排列: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. 例如: 1 .2 .3三个元素的全排列为: {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}. ------------------------------------------------------ 解法1(递归) 如下图:要对1.2.3.4进行

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • java中全排列的生成算法汇总

    全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来.任何n个字符集的排列都可以与1-n的n个数字的排列一一对应,   因此在此就以n个数字的排列为例说明排列的生成法. n个字符的全体排列之间存在一个确定的线性顺序关系.所有的排列中除最后一个排列外,都有一个后继:除第一个排列外,都有一个前驱.每个排列的后继都可以从它的前驱经过最少的变化而得到,全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法. 全排列的生成法通常有以下几种: 字典序法   递增进

  • 全排列算法的原理和实现代码

    全排列是将一组数按一定顺序进行排列,如果这组数有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的

  • JAVA用递归实现全排列算法的示例代码

    求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i

  • 全排列算法的非递归实现与递归实现的方法(C++)

    (一)非递归全排列算法基本思想是:    1.找到所有排列中最小的一个排列P.    2.找到刚刚好比P大比其它都小的排列Q,    3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P =  A1A2A3An ( Ai!=Aj , (1<=i<=n  , 1<=j<=n, i != j  ) )找到P的一个最小排列Pmin = P1P2P3Pn  有  Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目

  • java编程之AC自动机工作原理与实现代码

    java编程之AC自动机工作原理与实现代码

    在阅读本文之前,大家可以先参考下<多模字符串匹配算法原理及Java实现代码> 简介: 本文是博主自身对AC自动机的原理的一些理解和看法,主要以举例的方式讲解,同时又配以相应的图片.代码实现部分也予以明确的注释,希望给大家不一样的感受.AC自动机主要用于多模式字符串的匹配,本质上是KMP算法的树形扩展.这篇文章主要介绍AC自动机的工作原理,并在此基础上用Java代码实现一个简易的AC自动机. 1.应用场景-多模字符串匹配 我们现在考虑这样一个问题,在一个文本串text中,我们想找出多个目标字符串

  • Python实现希尔排序算法的原理与用法实例分析

    Python实现希尔排序算法的原理与用法实例分析

    本文实例讲述了Python实现希尔排序算法的原理与用法.分享给大家供大家参考,具体如下: 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 希尔排序的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高

  • Python字符串的全排列算法实例详解

    本文实例讲述了Python字符串的全排列算法.分享给大家供大家参考,具体如下: 题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba. 输入描述 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母. 注意有可能重复,因此需要判断 注意list的append方法和list的+方法的区别 append方法在list后面添加元素 +方法在list后面添加l

  • Java实现雪花算法的原理

    Java实现雪花算法的原理

    SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法.其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id.在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的,后面的代码中有详细的注解. 这 64 个 bit 中,其中 1 个 bit 是不用的,然后用其中的 41 bit 作为毫秒数,用 10 bit 作为工作机器 id,12 bit 作为序列号. 给大家举个例子吧,比如下面那个 64 bit 的 long 型数字: 第一个部分

  • Java实现雪花算法的原理和实战教程

    Java实现雪花算法的原理和实战教程

    目录 SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法.其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id.在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的,后面的代码中有详细的注解. 这 64 个 bit 中,其中 1 个 bit 是不用的,然后用其中的 41 bit 作为毫秒数,用 10 bit 作为工作机器 id,12 bit 作为序列号. 给大家举个例子吧,比如下面那个 64 bit 的 long 型数字: 第一

  • Java 负载均衡的 5 种算法实现原理

    Java 负载均衡的 5 种算法实现原理

    目录 一.负载均衡算法简介 1.轮询法 2.随机法 3.源地址哈希法 4.加权轮询法 5.加权随机法 二.代码实现负载均衡五种算法 1.轮询法 2.加权轮询法 3.随机法 4.加权随机 5.源地址哈希法 前言: 什么是负载均衡: 指由多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的辅助.通过某种 负载分担技术,将外部发送来的请求均匀分配到对称结构中的某一台服务器上,而接收到请求的服务器独立地回应客户的请求.负载均衡能够平均分配客户请求

随机推荐