精华内容
下载资源
问答
  • 递归排列问题

    2017-07-14 11:20:48
    递归排列问题

    问题描述:

    给定一个数组,求数组元素的排列问题

    算法思路:

    采用递归的思想,设定集合R={r1,r2,r3,r4},Ri=R-ri,集合R中的元素的全排列记为P(R)
    首先我们分为两种情况,R集合中只有一个元素和R集合中有多个元素
    情况1:R集合中只有一个元素,这时集合R的全排列就只有一个
    情况2:R集合中有多个元素,这时我们可以递归的进行求解。

    举例说明:

    集合R中有两个元素时:全排列为以r1开头的全排列加上以r2开头的全排列,这时只有{r1,r2}和{r2,r1}
    集合R中有三个元素时:全排列为以r1开头的全排列加上以r2开头的全排列加上以r3开头的全排列,以r1开头的全排列进行分析,由于首位已经固定,所以我们可以直接考虑剩余元素{r2,r3}的全排列,然后在他们的全排列前加上r1就可以;求解{r2,r3}的全排列就可以参考集合中有两个元素时的情况,这样就可以将所有的情况递归的求解出来。
    集合R中有四个元素时:同理,先分解为三个,然后两个,然后一个……

    代码

    public static void getPermutation(int[] array,int i,int n){
            if(i==n){
                for(int j=0;j<=n;j++){
                    System.out.print(array[j]+" ");
                }
                System.out.println();
            }else{
                for(int j=i;j<=n;j++){
                    int temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                    getPermutation(array, i+1, n);
                    temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
        }

    运行结果

    这里写图片描述

    反思

    通过结果我们可以发现当数组中没有重复元素时,结果是对的,但是当数组中出现了重复元素时,结果就不正确,出现了很多重复的结果。这时候,我们可以利用set集合的元素不能重复的特性,先将结果保存在set中,然后在打印set中排列的结果。修改后的代码如下:

    public static void getPermutation(int[] array,int i,int n){
            if(i==n){
                StringBuffer s=new StringBuffer();
                for(int j=0;j<=n;j++){
                    s.append(array[j]+" ");
                }
                set.add(s.toString());
            }else{
                for(int j=i;j<=n;j++){
                    int temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                    getPermutation(array, i+1, n);
                    temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
        }

    然后在main函数中直接输出

    System.out.println(Arrays.toString(set.toArray()));

    运行结果如下
    这里写图片描述

    展开全文
  • 递归-排列问题

    2021-03-10 19:41:56
    递归-排列问题 问题描述: 设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}。集合x中元素的全排列记为Perm(X)。 (ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。 R的全排列可归纳如下: ...

    递归-排列问题

    问题描述:

    • 设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}。集合x中元素的全排列记为Perm(X)。
      (ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。
      R的全排列可归纳如下:
      当n=1时,Perm®=®,其中r是集合中唯一的元素;
      当n>1时,Perm®由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)…(rn)Perm(Rn)构成*。
    void perm(int list[],int start,int end1)
    {
        int i;
        if(start == end1)
        {
            for(i = 0;i <= end1;i++)
                cout << list[i];
                cout<<endl;
        }
        else
           {
             for(i = start; i <= end1; i++){
       swap(list[start], list[i]); //交换k, i 位置
       perm(list, start + 1, end1);
       swap(list[start], list[i]); //还原
           }
    }
    } 

    全码:

    在这里插入图片描述

    具体解析:

    在这里插入图片描述

    展开全文
  • 临近ACM大赛了,博主正在复习递归,毕竟博主是一个菜鸟,对递归总是有太多的疑问,所以搜罗了一些资料集中细谈一下用递归处理的排列组合问题 题目:用递归算法输出Cn m(从m中取n个数)的每一次的值; 代码如下: #...

    临近ACM大赛了,博主正在复习递归,毕竟博主是一个菜鸟,对递归总是有太多的疑问,所以搜罗了一些资料集中细谈一下用递归处理的排列组合问题

    题目:用递归算法输出Cn m(从m中取n个数)的每一次的值;

    代码如下:

    #include <iostream>

    using namespace std;

    int N,M,n;//N,M为题中的N,M;n为控制第一个位置的数

    int sz[100];//用来存储排列出的数值

    void print()//输出个数

    {

    for(int i=1;i<=n;i++)

    cout<<sz[i]<<" ";

    cout<<endl;

    }

    void f(int i)//递归函数

    {

    n++;//第一位的值

    for(;i<=M&&n<=N;i++)

    {

    sz[n]=i;

    if(n==N)

    print();

    f(i+1);

    }

    n--;

    }

    int main()

    {

    cin>>N>>M;

    n=0;

    f(1);

    return 0;

    }


    展开全文
  • 排列问题 递归解法

    2021-03-27 22:45:59
    排列问题 关键问题是每次的swap转化问题前缀 #include<iostream> using namespace std; void perm(int list[], int k, int m){ if(k == m){ for(int i = 0; i <= m; i++){ //输出list ...

    排列问题

    关键问题是每次的swap转化问题前缀

    #include<iostream>
    using namespace std;
    
    void perm(int list[], int k, int m){
    	
    	if(k == m){
    		
    		for(int i = 0; i <= m; i++){
    			//输出list 
    			cout << list[i];
    		}
    		cout << endl;
    		
    	} 
        else {
    		
    		for(int i = k; i <= m; i++){
    			swap(list[k], list[i]);
    			perm(list, k + 1, m);
    			swap(list[k], list[i]); //还原
    		}
    	}
    }
    
    void swap(int &a, int &b){
    	int temp = a;
    	a = b;
    	b = temp;
    }
    
    int main(){
    	int a[3] = {1, 2, 3};
    	perm(a, 0, 2);
    	return 0;
    }
    
    展开全文
  • 递归求全排列问题学习

    千次阅读 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;/****...
  • 算法笔记——【递归排列问题,整数划分问题,Hanoi问  递归的概念想必大家都清楚,概念神马的直接略过。这里介绍递归相关的几个问题。  1、排列问题  设R={r1,r2,...,rn}是要进行排列的n个元素...
  • 递归解决排列问题

    2009-03-30 15:24:15
    递归解决排列问题 关键字: 排列 引用 一根很细的竹竿27cm,在3cm,7cm,11cm,17cm,23cm 处各有一只蚂蚁,蚂蚁每秒钟走1cm,不能停,可以向左走也可以向右走,当两只蚂蚁碰头后都掉头往回走,蚂蚁不能相互超越,...
  • 【题目】设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 【算法讲解】 设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列...
  • 递归排列组合问题

    2018-03-13 09:01:00
    全排列递归求解 1 public class Main { 2 3 //思路:对每一个子递归的数组(除去第一个数的数组)进行全排列,并用除去的第一个数对所有子数组的全排列的每一项进行交换 4 5 public static void swap...
  • 求多个数组之间元素的排列组合问题,方法有两个:递归法、循环法。  首先应该认识到的是:  所有可以用递归实现的操作都可以转化为用while、for等循环实现。 递归法 优缺点: 数组数量不太多时...
  • 排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。 详细定义参考:...
  • 递归算法之排列问题

    2017-03-08 14:25:54
    *排列问题,对王晓东的《算法设计与分析》3,做了些改动,加入了一个 *const int start,可以决定所有排列从第几个元素开始输入,个人觉得 *书上的从0开始输出不好(指的是第17行,若我的代码没有被修改) *...
  •  ele为参与排列的个元素出现的个数  i为pl中下标 假设参与排列的元素有ABCD run(ele,int i){  {   递归收敛判断;  收敛后进行处理;  }  //递归块1  { 若元素A的个数不为...
  • 排列问题描述:如输入字符串“ABC”,调用递归函数将生成一个排列集合:{"ABC", "ACB", "BAC", "BCA", "CAB", "CBA"}也就是3!=6个非空子集。而对于字符...
  • 递归排列问题

    千次阅读 2006-02-17 16:09:00
    #include using namespace std;void swap(char &i,char &j){ char temp = i; i = j; j = temp;} void perm(char list[],int k,int m){ if(k==m) { for(int i=0;i cout cout
  • 递归-排列组合问题

    2016-04-12 22:35:27
    //一组数的所有排列组合 #include using namespace std;template void Perm(Type list[], int k, int m){ //将数组 k~m 的数进行排列作为后缀 if(k == m){ //排列到最后一个数,输出数组 for
  • 在后续的博文再总结一下排序算法的问题 2. 找中位数与其个数 这一步是最关键的,基本上这个写出来,程序已经算是完成8成了。 以中位数为起点,向两边比较得出中位数的个数,并记录中位数到两边的位置。 这里会...
  •  1、排列问题  设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}。集合x中元素的全排列记为Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳如下:  当n=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,483
精华内容 993
关键字:

递归排列问题