全排列递归算法

给出一个递归算法;

1、将一个n维数组初始化,第0位填1,第1位填2.。。。。。 第n-1位填n;

2、将数组看为两部分,一个是已排好的,剩下是待排的,分别用两个指针指向;

3、将第一个字符,依次与后n-1个字符交换值,每次交换得到一个新的首数字;

4、剩下的n-1个数字按2、3步骤重复直至所有数组完成排列;

使用c++实现,代码还有些繁琐,明天再仔细看看优化一下

1 #include<iostream>
2 using namespace std;
3
4 void swap(int  *p1,int *p2)
5 {
6     //交换p1和p2指向的值
7     int tmp=*p1;
8      *p1=*p2;
9     *p2=tmp;
10 }
11 void output(int *p,int n)
12  {
13     while(n>0)
14     {
15          cout<<*p;
16         p++;
17         n--;
18     }
19     cout<<"\n";
20 }
21
22 void fill(int *p1,int *p2,int  len,int n)
23 {//p1指向已填满的部分,始终指向第一个;
24     //p2指向尚余下的部 分,待插入那个;
25     //len表示已填部分的长度,n表示数组长度
26     if (len==n-1)
27         {
28             output(p1,n);//输出全部数 组
29         }
30     else
31     {
32         int  *p3,*p4;
33         int *pp=(int *)malloc(n*sizeof(int));
34          for(int i=0;i<n;i++)
35         {
36             * (pp+i)=*(p1+i);
37         }
38         p3=pp;
39          while(*p3!=*p2)
40         {
41             p3++;
42          }
43         p4=p3;
44
45         for(int  i=0;i<n-len;i++)
46         {
47             swap (p3,p4);
48             p4++;
49             fill (pp,p3+1,len+1,n);
50         }
51     }
52 }
53
54 void  inti(int *p,int n)
55 {//将数组中所有的元素全部初始化,
56     int  num=1;
57     while(num<=n)
58     {
59          *p=num++;
60         p++;
61          //cout<<num<<endl;
62     }
63 }
64 
65 int main()
66  {
67     int *p,n;
68     cout<<"请输入全排列规模:";
69      cin>>n;
70     p=(int *)malloc(n*sizeof(int));
71     inti (p,n);
72     fill(p,p,0,n);
73     return 0;
74 }

时间: 2024-10-02 07:36:26

全排列递归算法的相关文章

全排列的递归与非递归实现浅析

全排列问题在公司笔试的时候很常见,这里介绍其递归与非递归实现. 递归算法 1.算法简述 简单地说:就是第一个数分别以后面的数进行交换E.g:E = (a , b , c),则 prem(E)= a.perm(b,c)+ b.perm(a,c)+ c.perm(a,b)然后a.perm(b,c)= ab.perm(c)+ ac.perm(b)= abc + acb.依次递归进行. void swap(string &pszStr,int k,int m) { if(k==m) return ; c

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

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

使用C语言解决字符串全排列问题_C 语言

问题输入一个字符串,打印出该字符串中字符的所有排列.例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba 思路这是典型的递归求解问题,递归算法有四个特性:     必须有可达到的终止条件,否则程序陷入死循环     子问题在规模上比原问题小     子问题可通过再次递归调用求解     子问题的解应能组合成整个问题的解 对于字符串的排列问题: 如果能生成n-1个元素的全排列,就能生成n个元素的全排列.对于只有一个元素的集合,可以直接生

C语言递归操作用法总结_C 语言

本文实例总结了C语言递归操作用法.分享给大家供大家参考,具体如下: 用归纳法来理解递归 步进表达式:问题蜕变成子问题的表达式结束条件:什么时候可以不再是用步进表达式直接求解表达式:在结束条件下能够直接计算返回值的表达式逻辑归纳项:适用于一切非适用于结束条件的子问题的处理,当然上面的步进表达式其实就是包含在这里面了. 递归算法的一般形式: void func( mode) { if(endCondition) { constExpression //基本项 } else { accumrateEx

排列和组合算法的实现方法_C语言经典案例_C 语言

排列和组合算法是考查递归的常见算法,这两种算法能用递归简洁地实现. 本人在经过多次摸索和思考之后,总结如下,以供参考. 程序代码如下: #include <stdio.h> #include <stdlib.h> char array[] = "abcd"; #define N 4 #define M 3 int queue[N] = {0}; int top = 0; int flag[N] = {0}; void perm(int s, int n) { i

求字符串全排列的递归算法(java程序)

import java.util.ArrayList; import java.util.List; /** * 求字符串的全排列 * * @author wenin819 * */ public class Arrange { /** * 判断调用求排列的主要方法 */ public static List<String> arrange(String input){ if(null == input || 0 == input.length()){ System.out.println(&

PHP全排列算法实现程序代码

  从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 共3*2*1=6种 3! 2公式 全排列数f(n)=n!(定义0!=1) 递归算法 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1 3,1,2 这是由于算法只是考虑到了如何输出全排列,而没有考虑到换位是否有问题.所以我提出了解决

c#-C#怎么对4个数字做全排列并赋值给4个变量?

问题描述 C#怎么对4个数字做全排列并赋值给4个变量? 例如对已有的4个数字例如(1234)做全排列并赋值给a1a2a3a4?对每个a1a2a3a4的情况都要做一些操作的,就是想不明白怎么用循环之类的得出那4个变量的24种不同的情况 解决方案 是这个意思么? int[] array = {1 2 3 4}; int iCount = 0; for (int i1 = 0; i1 < 4; i1++) { for (int i2 = 0; i2 < 4; i2++) { if (i2 == i1

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

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