精华内容
下载资源
问答
  • 递归求全排列.rar 递归求全排列.rar 递归求全排列.rar 递归求全排列.rar 递归求全排列.rar 递归求全排列.rar 递归求全排列.rar
  • 递归求全排列

    2021-06-24 18:30:05
    算法笔记–胡凡 4.3.2 #include<iostream> using namespace std; const int maxn = 11; int n,P[maxn],hashTable[maxn] = {false}; void generateP(int index) { if(index == n + 1) ... }

    算法笔记–胡凡 4.3.2

    #include<iostream>
    using namespace std;
    const int maxn = 11;
    
    int n,P[maxn],hashTable[maxn] = {false};
    void generateP(int index)
    {
    	if(index == n + 1)
    	{
    		for(int i=1;i<=n;i++)	
    			printf("%d",P[i]);
    	
    	printf("\n");
    	return ;
    	} 
    	for(int x = 1; x <= n; x++)
    	{
    		if(hashTable[x] == false)
    		{
    			P[index] = x;
    			hashTable[x] = true;
    			generateP(index + 1);
    			hashTable[x] = false;
    		}
    	}
    }
    int main()
    {
    	n = 3;
    	generateP(1);
    	return 0;
    	
    	
    	
    	return 0;
     } ```
    
    
    展开全文
  • 递归求全排列

    题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1384

    题目给出一个长度不超过9的字符串,字符串由0~9这些组成,然后从小到大输出这些字符的全排列,

    坑点,重复的串不要输出,可以搞一个map映射一下。

    考察知识:递归


    AC代码:

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <map>
    #define inf 0x3f3f3f3f
    
    using namespace std;
    
    char a[15];
    char ans[15];
    int vis[15];
    int len;
    map<string,int>m;
    void dfs(int pos)
    {
        if(pos == len)
        {
            ans[len] = '\0';
            if(m[ans]==0)  ///不能输出重复的。
            {
                m[ans]=1;
                puts(ans);
            }
            return;
        }
        for(int i = 0; i < len; i++)
        {
            if(vis[i]==0)
            {
                ans[pos] = a[i];
                vis[i] = 1;
                dfs(pos+1);
                vis[i] = 0;
            }
        }
    }
    int main()
    {
        while(~scanf("%s",a))
        {
            len = strlen(a);
            sort(a,a+len);
            memset(vis,0,sizeof(vis));
            m.clear();
            dfs(0);
        }
        return 0;
    }
    



    展开全文
  • Java递归求全排列详解

    2020-10-06 21:19:55
    Java递归求全排列详解 推荐博客: 博客园Java全排列递归算法,结尾的解释很形象了 csdn的大佬写的,和我下面的代码思路基本一致 全排列的递归解释: 全排列的数学定义就不再过多解释,考虑递归算法的实现可从下面...

    Java递归求全排列详解


    推荐博客:
    博客园Java全排列递归算法,结尾的解释很形象了
    csdn的大佬写的,和我下面的代码思路基本一致

    全排列的递归思想解释:

    全排列的数学定义就不再过多解释,考虑递归算法的实现可从下面几点入手(以数组为例,如对其他元素排列,将元素编号放入数组即可):

    1、一个数的全排列,如排列{1},就是这个数本身这一种情况

    2、两个数的全排列,如排列{1,2}:

    第一步:将{1}放在第零个位置,剩下的{2}进行一个数的全排列,结果为{1,2}

    第二步:将{2}放在第零个位置,剩下的{1}进行一个数的全排列,结果为{2,1}

    即两个数的全排列为以上2种情况。
    3、三个数的全排列,如排列{1,2,3}:

    第一步:将{1}放在第零个位置,剩下的{2,3}进行两个数的全排列,结果为{1,2,3} {1,3,2}
    第二步:将{2}放在第零个位置,剩下的{1,3}进行两个数的全排列,结果为{2,1,3} {2,3,1}
    第三步:将{3}放在第零个位置,剩下的{1,2}进行两个数的全排列,结果为{3,1,2} {3,2,1}

    即三个数的全排列为以上6种情况。

    4、即m个数(无重)的全排列,就是将m个数分别放在第零个位置,再将剩下的m-1个数的全排列加在后面,当m-1=1时为递归>的出口。

    代码

    注意点

    • 一个数的全排列就是其本身

    程序的主要思路是:参考文章

    把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数23做全排列。
    
    把第2个数换到最前面来,准备打印2xx,再对后两个数13做全排列。
    
    把第3个数换到最前面来,准备打印3xx,再对后两个数12做全排列。
    
    可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题
    
        解题过程:
    
       (1) 当 N = 1的时候,则直接打印数列即可。
    
       (2) 当 N = 2的时候,设数组为 [a, b]
    
                打印a[0], a[1] (即a,b)
    
                交换a[0],a[1]里面的内容
    
                打印a[0],a[1]   (此时已变成了 [b, a](3) 当 N = 3的时候,数组为 [a, b, c]
    
     把a放在 a[0] 的位置(原本也是如此,a[0] = a[0]),打印b,c的全排列(即a[1], a[2]的全排列)
                           a  b  c
    
                           a  c  b
    
     把b放在a[0]的位置(这时候需要交换原数组的a[0]和a[1]),然后打印a, c的全排列
                           b   a  c
    
                           b   c  a                       
    
     打印完后再换回原来的位置,即a还是恢复到a[0],b还恢复到a[1]的位置
    
     把c放在a[0]的位置(这时候需要交换的是原数组的a[0]和a[2]),然后打印a, b的全排列
                 c  b  a
                 c  a  b
     打印完后再换回原来的位置,即a还是恢复到a[0],b还恢复到a[1]的位置,至此,全排列完成
     当 N = 456,……的时候,以此类推。
    
    	//全排列函数(递归),参数k是确定第k个位上的字符
    	//k是数组元素下标,从0开始,所以递归终止条件中arr.length可以不减1,结果一样的
    	private static void f(char[] arr, int k) {
    		if (k == arr.length-1) {
    			System.out.println(arr);
    		}
    		
    		for (int i = k; i < arr.length; i++) {
    			//交换位置
    			char t = arr[k];
    			arr[k] = arr[i];
    			arr[i] = t;
    			
    			f(arr, k+1);
    			
    			//回溯
    			t = arr[k];
    			arr[k] = arr[i];
    			arr[i] = t;
    		}
    	}
    

    无重复元素测试

    public class Test{
    
    	public static void main(String[] args) {
    		char[] cArr={'A','B','C'};
    		f(cArr,0);
    		
    	}
    
    	//全排列函数(递归),参数k是确定第k个位上的字符
    	//k是数组元素下标,从0开始,所以递归终止条件中arr.length可以不减1,结果一样的
    	private static void f(char[] arr, int k) {
    		if (k == arr.length-1) {
    			System.out.println(arr);
    		}
    		
    		
    		for (int i = k; i < arr.length; i++) {
    			char t = arr[k];
    			arr[k] = arr[i];
    			arr[i] = t;
    			
    			f(arr, k+1);
    			
    			//回溯
    			t = arr[k];
    			arr[k] = arr[i];
    			arr[i] = t;
    		}
    	}
    }
    
    

    运行结果

    在这里插入图片描述

    有重复元素测试结果

    使用AAB测试,结果有重复项
    在这里插入图片描述

    如何去重?

    可以在全局new一个set(注意使用static),然后每次把全排列的结果add到set里就可以了
    详见博客https://yinglongwu.blog.csdn.net/article/details/108833986

    展开全文
  • 递归求全排列(dfs)

    2019-03-13 16:41:35
    递归求全排列(dfs) 一张图看懂。 交换 递归 回溯 #include &lt;cstdio&gt; #include &lt;vector&gt; #include &lt;queue&gt; #include &lt;cstring&gt; #include &lt;cmath...
    递归求全排列(dfs)

    一张图看懂。

    • 交换
    • 递归
    • 回溯
      在这里插入图片描述
    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <cstring>
    #include <cmath>
    #include <map>
    #include <set>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    #include <stack>
    #include <ctime>
    #include <cstdlib>
    //#pragma comment (linker, "/STACK:256000000")
    using namespace std;
    #define db(x) cout<<x<<endl
    
    typedef long long ll;
    const int N = 200 + 10;
    const int INF = 0x3f3f3f;
    
    void print(int x[])
    {
        for(int i = 0; i < 4; i++){
            printf("%d ", x[i]);
        }
        cout << endl;
    }
    void f(int x[], int k)
    {
        int i, t;
        if (k >= 4)
        {
            print(x);
            return;
        }
        for (i = k; i < 4; i++)
        {
            {                  
                t = x[k];
                x[k] = x[i];
                x[i] = t;
            }
            f(x, k + 1);
            {                  
                t = x[k];
                x[k] = x[i];
                x[i] = t;
            }
        }
    }
    int main()
    {
        int x[] = {1, 2, 3, 4};
        f(x, 0);
        return 0;
    }
    
    
    展开全文
  • 递归求全排列的学习与理解 全排列: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 比如:求1~3的全排列 由中学的...
  • 递归求全排列算法

    2012-08-13 11:19:23
    递归求算排列算法;递归求算排列算法;递归求算排列算法;
  • 递归求全排列

    2020-07-10 14:19:57
    *递归打印全排列 */ #define Swap(a,b){int temp = a; a=b; b=temp;} int data[] = {1,2,3,4,5,6,7,8,9,10,32,15,18,33}; int num = 0; //统计全排列的个数 int Perm(int begin, int end){ int i; if(begin == ...
  • 递归求全排列问题学习

    千次阅读 2009-11-17 12:33:00
     递归求全排列,时间复杂度为指数级。 一个常用的递归算法,用C++代码实现。只是实现了核心递归功能,没有包装程序。 #include #include using namespace std;int x[6]={10,2,30,4,5,6};static int count=0;/****...
  • PREV-3带分数(内含递归求全排列的套路)Java 前言 最开始看到这道题我是打算直接暴力解决,九个for循环写完后才发现,我却不知道怎么表示判定的条件,结果想了一会儿后,还是放弃了,现在看来其实也可以写的,就用下文的...
  • 使用递归求全排列

    2017-05-14 00:06:58
    全排列:如123三个数字的全排列:123,132,213,231,312,321;可以使用穷举的方式使用三个for循环来解决。但是如果数字很多或者数字的个数不确定...递归就是考虑当前的要做的是,下一步和当前的方法一样,要有结束条件。
  • 递归 求全排列与全组合

    千次阅读 2017-10-13 11:35:09
    递归
  • 递归求全排列。1-n

    2018-08-01 16:04:53
    #include&lt;iostream&gt; using namespace std; const int maxn=11; int n,p[maxn],hashTable[maxn]={false}; void generateP(int index){ if(index==n+1) { for(int i=1;...,p[i...
  • 全称“分而治之”, 分治法作为一种算法思想,既可以使用递归的手段去实现,也可以通过非递归的手段去实现。 递归 递归边界和递归式构成。 //求n的阶乘 #include&lt;stdio.h&gt; #include&lt;string....
  • 同学遇到的面试问题,大意是M台机器放在N个房间,不使用递归求打印所有情况 解题思路:情况共计N**M种。开始想将所有情况放入数组,填充好数组再逐个打印。随后发现按照填充的思路,不使用大数组也可以实现。思路是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 995
精华内容 398
关键字:

递归求全排列