精华内容
下载资源
问答
  • M个元素取N个元素组合

    千次阅读 2018-11-23 14:50:04
    #将核心的部分改为泛型 /** * @author Bob.chen ... * @desc 组合,从M个元素取N个元素组合 */ public class Combination { /** * * @desc * @author Bob.chen * @param input 输入 * @para...

    #将核心的部分改为泛型

    /**
     * @author Bob.chen
     * @date 2018年11月22日-下午2:47:50
     * @desc 组合,从M个元素中取N个元素组合
     */
    
    public class Combination {
    
    	/**
    	 * 
    	 * @desc 
    	 * @author Bob.chen   
    	 * @param input 输入
    	 * @param output 临时保存组合
    	 * @param index 长度索引
    	 * @param start 开始索引
    	 * @param r void 返回值
    	 * @throws
    	 */
    	public <E> void dfs(E[] input, E[] output, int index, int start,List<List<E>> r) {
    		if (index == output.length) {
    			r.add(Lists.newArrayList(output));
    		} else {
    			for (int j = start; j < input.length; j++) {
    				output[index] = input[j];
    				dfs(input, output, index + 1, j + 1,r);
    			}
    		}
    	}
    
    	private static class CombinationHandler {
    		private static Combination instance = new Combination();
    	}
    
    	private Combination() {
    	}
    
    	public static Combination getInstance() {
    		return CombinationHandler.instance;
    	}
    	
    	public static void main(String[] args) {
    		String[] input = { "A", "B", "C","D"};
    		int N = 2;// 组合长度
    		String[] output = new String[N];
    		List<List<String>> r = new ArrayList<List<String>>();
    		Combination.getInstance().dfs(input, output, 0, 0,r);
    		System.out.println(r);
    	}
    }
    
    
    展开全文
  • 如A{1,2,3}则有这些组合:a) 1,2,3; b) 12,13,23; c) 123; 很显然这是一个组合问题,对于组合最常规的算法...2)对于f(n,m),我们从数组中任意个元素,然后再从剩下的n-1个元素取m-1个元素,既f(n-1,m-1); 3)

    n个元素中取m个元素的组合

    如A{1,2,3}则有这些组合:1,2,3,12,13,23,123;

    我们可以把问题分解如下:
    1)求数组中由1到n个元素的组合f(n,m) (m>=1 && m<=n;n为数组元素个数);
    2)对于f(n,m),我们从数组中任意取一个元素,然后再从剩下的n-1个元素中取m-1个元素,既f(n-1,m-1);
    3)重复第2步,直到f(n-m+1,1),即从n-m+1个元素中取出最后一个元素;
    4)把有效的组合压栈,并在压栈前判断该组合在栈中是否存在,避免由于数组元素的重复而导致组合重复。

    <script language="javascript"  type="text/javascript">  
    var result = new Array();  //保存所有组合的数组  
    function getAllComb(myarr)  
    {  
     var len=myarr.length;  
     for(var i=1;i<=len;i++)  
      getComb(myarr,len,i);  
     document.write("数组("+myarr.join(",")+")的所有的组合(共"+ result.length+"种)如下:<hr>"+result.join("\t"));  
    }  
      
    //从数组myarr(n)中任选m个元素的所有组合(m>=1 && m<=n)。  
    function getComb(myarr,n,m,rs)  
    {  
     if(rs==null)  
      rs = new Array();  
     for(var i=n;i>=m;i–)  
     {  
      rs[m-1]=myarr[i-1];      //取出第n个元素作为组合的第一个元素  
      if(m>1)  
       getComb(myarr,i-1,m-1,rs);  //递归,在n-1个元素中取m-1个元素,直到取出最后一个元素  
      var comb = rs.join("");     //获得一个组合  
      if(!checkExist(result,comb))  
       result.push(comb);  
     }  
    }  
      
    //查找某元素是否存在数组中,存在返回true,不存在返回false  
    function checkExist(myarr,e)  
    {  
     for(var i=0;i<myarr.length;i++)  
      if(e==myarr[i]) return true;  
     return false;  
    }  
      
    //测试  
    var arr=new Array(1,2,3,3,4,5);  
    getAllComb(arr);  

    输出结果:

    数组(1,2,3,3,4,5)的所有的组合(共47种)如下:


    5 4 3 2 1 45 35 25 15 34 24 14 33 23 13 12 345 245 145 335 235 135 125 334 234 134 124 233 133 123 3345 2345 1345 1245 2335 1335 1235 2334 1334 1234 1233 23345 13345 12345 12335 12334 123345


    深度优先算法求含有N个元素的集合的全部组合

    先来看另外一道题:给定整数:a1, a2, a3.....an, 判断是否可以从中选出任意个数,使其和等于K, (数字的个数,取1--N个数都可以),这道题要求找出这N个数中选1,2,3...N个元素的所有组合,如果任何一个组合满足和为K, 就找到了答案,

    所以:本质上,这道题就是要求出这个集合的所有的组合,怎么求所有的组合? 

    我的理解:对任何元素a 属于A集合, 求子问题1 (包含这个元素时的组合),再加上子问题 2(不包含这个元素的组合),子问题1和子问题2本质上又是和包含这两个子问题的父问题本质上是一样的,所以用递归可以解决:

    #include <string>
    #include <iostream>
    using namespace std;
    char* arry[] = {"a", "b", "c", "d", "e"};
    void DfsCombination(int n, string& out){
        if (n == sizeof(arry)/sizeof(char *)){
        if(!out.empty())
            cout << out <<endl;
        return;
    }
    // 不加上a[i]的情况
    DfsCombination(n + 1,  out);
    // 加上a[i]的情况
    DfsCombination(n + 1, out + arry[n]);
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
        string output;
        DfsCombination(0, output);
        system("pause");
        return 0;
    }

    递归实现组合数打印,C(n,m),从n个数中选出m个数(m<=n)个的全部组合打印。

    先看一个例子:
                C(5,3) = 10
                   1 2 3
                   1 2 4
                   1 2 5
                   1 3 4
                   1 3 5
                   1 4 5
                   2 3 4
                   2 3 5
                   2 4 5
                   3 4 5

    大家注意到没有,
                   1 | 2 3
                   1 | 2 4
                   1 | 2 5
                   1 | 3 4
                   1 | 3 5
                   1 | 4 5
     
                  ------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。


                   2 | 3 4
                   2 | 3 5
                   2 | 4 5
     
                  ------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。


                   3 | 4 5 
                  ------ C(2, 2)∵只能在{4, 5}中挑2个出来。
                   
    这样就很容易写出递归算法来。

    Algorithm combination(n, k, A[l..n+l-1])
    if k = 0
       print ary[1..k]
    else 
       for i←1 to n-k+1
           ary[index++] = A[l+i-1]
           combination(n-i, k-1, A[l+i..n+l-1])
           --index
       endfor

    大家可能会疑惑干嘛要弄出个index,还有一加一减的(你手工算一下就知道了)。
    可以在pku acm 2245 Lotto 上试一试。个数中选出m个数(m<=n)个的全部组合打印。

    int *dst_array,top=0;//中间数组,存放中间求解过程,count计数所有的组合个数
    int cnt = 0;
    //打印长度为n的数组元素
    static void printA(int*parray,int n)
    {
        int i;
        for(i=0;i<n;i++)
        {
            printf("%d ",parray[i]);
        }
    }
    //递归打印组合数
    static  void print_combine(int *pArray,int n,int m)
    {
        if(n < m || m==0)  
        {
               return ;//情况一:不符合条件,返回
        }
        print_combine(pArray+1,n-1,m);//情况二:不包含当前元素的所有的组合
        dst_array[top++]=pArray[0];//情况三:包含当前元素
        if(m==1)
       {  //情况三-1:截止到当前元素
            printA(dst_array,top);
            printf("\n");
            cnt++;
            top--;
            return;
        }
        print_combine(pArray+1,n-1,m-1);//情况三-2:包含当前元素但尚未截止
        top--;//返回前恢复top值
    }
     
    int main()
    {
        int n,m,*parray;//存放数据的数组,及n和m
        printf("---以下实现从n个数中选出m个数的全组合打印(n个数为1,2,3....n---\n");
        printf("---请输入n 和m \n---");
        scanf("%d%d",&n,&m);
        printf("\n---以下是输出结果---\n");
        parray=(int *)malloc(sizeof(int)*n);
        dst_array=(int *)malloc(sizeof(int)*m);
        int i;
        for(i=0;i<n;i++)
        {
               //初始化数组
            //scanf("%d",&parray[i]);
               parray[i] = i+1;
        }
        print_combine(parray,n,m);//求数组中所有数的组合
        printf("=====C(%d,%d)共计:%d个=====",n,m,cnt);
        free(parray);
        free(dst_array);
        return 0;
    }


                n个元素中取m个元素的全排列

    全排列的要求:

    输入:字符串"abc"。

    输出:如下图示,


    思路1——全排列的递归实现核心思想

    比如对于字符串”abc”,

    第一步:求所有可能出现在第一个位置的字符即:a,b,c。

    使用方法:把第一个字符和后面的b、c字符进行交换。

    第二步:把第一个字符后面的所有字符仍然看成两部分,即后面的第一个字符及除此之外的其他字符。然后完成后面的第一个字符与其他字符的交换。比如:第2个位置的b与第3个位置c的交换。

    第三步:依次递归,直到末尾的’\0’为止。

    全排列的递归实现:

    static int g_sCnt= 0;
     
    //permutation的重载版本.
    voidpermutation(char* pStr, char* pBegin)
    {
           if(*pBegin == '\0')
           {
                  ++g_sCnt;
                  cout << pStr << endl;
           }
           else
           {
                  for(char* pCh = pBegin; *pCh != '\0'; ++pCh)
                  {
                         //从第一个字符依次和后面的字符进行交换.
                         char temp = *pCh;
                         *pCh = *pBegin;
                         *pBegin = temp;
     
                         permutation(pStr,pBegin+1);
                        
                         //交换回原样,以便再递归处理后面的字符.
                         temp = *pCh;
                         *pCh = *pBegin;
                         *pBegin = temp;
     
                  }//end for
           }//end else
    }
    
    int main()
    {
        char strSrc[] = "abcd";
        permutation(strSrc,strSrc);
        cout<< "共 " << g_sCnt << " 种排列!" <<endl;
        return 0;
    }

    思路2——全排列的STL实现:

    有时候递归的效率使得我们不得不考虑除此之外的其他实现,很多把递归算法转换到非递归形式的算法是比较难的,这个时候我们不要忘记了标准模板库STL已经实现的那些算法,这让我们非常轻松。

    STL有一个函数next_permutation(),它的作用是如果对于一个序列,存在按照字典排序后这个排列的下一个排列,那么就返回true且产生这个排列,否则返回false。

    注意,为了产生全排列,这个序列要是有序的,也就是说要调用一次sort。

    实现很简单,我们看一下代码:

     void permutation(char* str)
    {
           int length = strlen(str);
     
           //第1步:排序
        sort(str,str+length);
     
           //第2步:调用函数next_permutation
        do
        {
            for(int i=0; i<length; i++)
                  {
                         cout<<str[i];
                  }
            cout << endl;
        }while(next_permutation(str,str+length));
       
    }
     
    int main()
    {
        char str[] = "acb";
        permutation(str);
       
        return 0;
    }

    思路3:全排列的字典树实现



    展开全文
  • 使用回溯法求n个元素中去m个元素的c语言代码,包括2版本,递归版和迭代版,前者代码简洁,后者性能更好些。

    包含2个版本,第一个为递归版本,代码简洁,性能稍差。第二个为迭代版本,逻辑复杂,但性能更好。

     

    #include <stdlib.h>
    #include <stdio.h>
    //#include <windows.h>
    
    typedef char ELE_TYPE;
    #define ELE_FMT "%c"
    
    //int g_count=0;
    
    //元素类型和格式符号使用宏定义,很容易改为其他数据类型,如数组类型改为int,则格式符改为"%d ".
    void printCombo(int idx_arr[], ELE_TYPE eArr[],int m)
    {
        int i;
    	//g_count++;
    	//return ;
    	for (i=0;i<m;i++)
            printf(ELE_FMT,eArr[idx_arr[i]]);
        printf("\n");
    }
    
    // 递归形式的求组合数的函数combos,使用回溯法,求从n个元素中取m个元素的所有组合
    // 取到元素的序号保存在数组idx_arr[]中,以递增方式排列,每个序号的范围为从0到n-1
    // level为递归深度,取值范围为0到m-1,当level==m-1时, 所有的m个元素已经取到,打印这m个元素
    void combos(int n, int m, int idx_arr[], ELE_TYPE eArr[], int level )
    {
        int i,begin,end;
        if (level==0)
            begin=0;
        else
            begin=idx_arr[level-1]+1;
        
        end=n-m+level;
        for (i=begin;i<=end;i++)
        {
            idx_arr[level]=i;
            if ( level==m-1)
                printCombo(idx_arr,eArr,m);		//打印这m个个元素
            else
                combos(n,m,idx_arr,eArr,level+1); //继续取一个元素
        }
    }
    
    
    // 迭代形式的求组合数的子程序,该函数用于求n个元素中取m个元素的所有组合
    // 取到元素的序号保存在数组idx_arr[]中,以递增方式排列,每个序号的范围为从0到n-1
    // 其算法实质是不断地生成一个又一个的组合数,每次迭代对idx_arr中某个元素做更新操作
    
    // 在该子程序中,2个重要的变量mode和i用于控制更新操作,
    //   mode表示更新模式,其值为M_FILL或者M_INC。
    //   M_FILL表示填充模式,当mode为此模式,元素idx_arr[i]的值总是被设置为比上级元素idx_arr[i-1]大1的数
    //   M_INC 表示增量模式,当mode为此模式,元素idx_arr[i]的值总是递增1个单位
    
    //关于“超限”,对于从n个元素中任取m个元素,取到的每个元素的序号是0到n-1
    // 我们把取到的元素的序号按照增序排列,存入idx_arr数组
    // 例,当n=5,m=3时,如果取到的最后一个元素的序号大于4,或者取到的倒数第2个元素大于3,我们称之为超限。
    // 更一般的,取到的idx_arr[i] > n-m+i,则为超限
    
    // 这个子程序用到5个if和一个while,总共6次比较,显然,其逻辑要比上面的那个递归版本复杂的多。
    // 凡事有利就有弊,这个子程序的性能要比上面的递归版本好,
    // 我的试验表明,将输出子程序printCombo改为只做一次整数加法,当n=28,m=14,迭代版本的性能是递归版本的130%
    
    #define M_FILL 0   //填充模式
    #define M_INC  1   //递增模式
    
    void IterativeCombos(int n, int m, int idx_arr[], ELE_TYPE eArr[] )
    {
    	int i=0;  
    	int mode=M_FILL;
    	
    	while (i>=0)
    	{
    		if (mode==M_FILL)	//填充模式
    		{
    			if (i==0)
    				idx_arr[0]=0;
    			else
    				idx_arr[i] = idx_arr[i-1]+1;
    			
    			if (i == m-1)	//当前焦点已经达到最大深度
    			{
    				printCombo(idx_arr,eArr,m); //打印这个包含m个元素的组合
    				mode=M_INC;	//切换为增量模式	
    			}
    			else			//没有达到最大深度
    				i++;		//继续填充下级节点
    		}
    		else				//增量模式
    		{
    			idx_arr[i]++;	//焦点元素递增
    			
    			if ( idx_arr[i] > n-m+i ) //已经超限
    				i--;
    			else
    			{
    				if (i==m-1)		//当前焦点已经达到最大深度
    					printCombo(idx_arr,eArr,m); //打印这个包含m个元素的组合
    				else
    				{
    					i++;		 //继续填充下级节点
    					mode=M_FILL; //切换到填充模式
    				}
    			}
    		}
    	}
    }
    
    int main(int argc, char* argv[])
    {
        int i;
    
    #define N  6
    #define M  3
    
        ELE_TYPE eArr[N]; //定义6个数组的数组,
        int idx_arr[M];   //取到的3个元素的需要放在数组idx_arr中
    
    	for (i=0;i<sizeof(eArr)/sizeof(ELE_TYPE);i++) //数组的元素为'A'到'F'
            eArr[i]='A'+i;
    
    	combos(sizeof(eArr)/sizeof(ELE_TYPE),M,idx_arr, eArr, 0); //枚举所有6中取3的组合
    
    	IterativeCombos(sizeof(eArr)/sizeof(ELE_TYPE),M,idx_arr, eArr); //枚举所有6中取3的组合
    
        return 0;
    }
    


     

    展开全文
  • 如:1 2 3 4 3 则有1 2 3,1 2 4,1 3 4,2 3 4 public class mAn {  public static String str = "";  public static char a[];    public static void f(int n,int m){  if(n == 0){  S...

    如:1 2 3 4 取3个 则有1 2 3,1 2 4,1 3 4,2 3 4

    public class mAn {
        public static String str = "";
        public static char a[];
        
        public static void f(int n,int m){
            if(n == 0){
                System.out.println(str);
                return;
            }
            for(int i=m; i<a.length; i++){
                str += a[i]+" ";
                if(i+1 > a.length) return;
                f(n-1,i+1);
                str = str.substring(0, str.length()-2);
            }
            return;
        }
        
        public static void main(String[] args) {
            a = new char[]{'a','b','c','d'};
            //System.out.println(a[3]);
            f(3,0);
        }
     
    }

    展开全文
  • 排列的定义:从n个不同元素中,任取m(mn,mn均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一排列;从n个不同元素中取出m(mn个元素的所有排列的个数,叫做从n个不同...
  • 01. 问题 ... 算法: 从n个不同元素中取出m个元素组合数是多少? 这些组合分别是什么? (其中: n > 0; 0 < mn;) 02. 概念 排列组合组合学最基本的概念. 所谓排列, 就是指从给定数的元素...
  • ,有两种方法解决该问题,一种是用回朔法,用temp表示临时的一个m组合,用递归的方法对于temp中的元素弹出加入。第二种方法是借助数据结构栈。 emmm: 其实应该是同一种方法,第一种回朔法用了系统的栈空间,第二种...
  • #include<stdio.h> int fac(int x); int main() ... f=fac(m)/(fac(n)*fac(m-n)); printf("%d",f); return 0; } int fac(int x) { int ff=1; for(int i=1;i<=x;i++) { ff=ff*i; }
  • 排列组合n个元素中选取m个元素

    千次阅读 2017-05-16 21:42:30
    //n个元素中选m个 int n,m; Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); int[] array = new int[n]; for (int i = 0; i ; i++) { array[i] = in.nextInt(); } ...
  • 这道题比较简单,是常见的排列组合问题,由于之前的博客文章已经讨论的排列问题(集合的全排列),在此我们仅仅讨论一下组合的问题,n个元素集合中求m个元素的子集合: 我们在这里介绍的是递归的方法,思路如下: ...
  • 组合是一基本的数学问题,本程序的目标是输出从n个元素取m个的所有组合。 例如从[1,2,3]中取出2数,一共有3中组合:[1,2],[1,3],[2,3]。(组合不考虑顺序,即[1,2]和[2,1]属同一个组合) 本程序的思路(来自...
  • n)个元素,输出这m个元素所有不同的组合 分析: 举例如:1 2 3 4 5 从中选出任意3数的组合分别为: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 观察上述例子中,选择的步骤是这样的: 从{1,...
  • 3个元素,11个组合 苹果,梨子,桃子,选11组合c(n+m-1,m-1)=c(n+m-1,n)#define _CRT_SECURE_NO_WARNINGS #include #include int main() { int k = 0; for (int i1 = 1; i1 ; i1++) { for (int i
  • package reverse; public class Cat { public static void main(String[] args) { int[] s = {4, 2, 1, 3, 0, 5}; String tmp = ""; for(int i=1;i tmp = tmp + s[i]; } ...int l
  • iOS之从N个数里面取M个数的组合算法

    千次阅读 2020-08-27 21:52:02
    数组 data 有 N 个元素,从中选取 M 数的组合 array(不分顺序),可使用递归算法实现,过程如下: 选择 data 的第 1 个元素为 array 的第一个元素,即:array[0] = data[0]; 在 data 第一个元素之后的其它...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 排列组合是一基本的数学问题,本程序的目标是输出从n个元素取m个的所有排列、组合
  • TODO:排列组合问题:n个数中取m个 排列组合组合学最基本的概念。所谓排列,就是指从给定数的元素中取出指定数的元素进行排序。组合则是指从给定数的元素中仅仅取出指定数的元素,不考虑排序。排列...
  • ​​算出从n个不同元素中取出m个元素mn)的组合数。 建议定义和调用函数fact(n)计算n!,其中n的类型是int,函数类型是double。 输入格式: 输入在一行中给出两正整数mnmn),以空格分隔。 输出格式: ...
  • java代码-从n个值里取m个值的全部组合方式(不重复)
  • Python中实现排列组合,从M个元素中有序或者无序选取N个元素的集合。 import itertools '''无序排列''' c = list(itertools.combinations([1, 2, 3, 4], 2)) print(c) '''有序排列''' p = list(itertools....
  • 假如现在有n个数,分别从里面选择m个出来,那么一共有多少种不同的组合呢,分别是哪些呢? 利用计算机的计算力,采用回溯算法很容易求解 程序源代码如下: #include&lt;iostream&gt; #include&lt;...
  • #include int factorial(int ... printf("%d",factorial(m)/(factorial(n)*factorial(m-n))); return 0; } ![图片说明](https://img-ask.csdn.net/upload/201912/10/1575940556_955774.png) 求大佬指点哪错了? ``` ```
  • m个数中取n个数的组合

    千次阅读 2013-05-30 01:51:58
    #include int a[1000]; int end; // 保存输入要n值 // 从m个数中,取出n个数的组合 void Combination(int m, int n) { int i, j;...// 最后一位置的元素可以取m,m-1,m-2.....n if (n > 1) {
  • n个数,从中取m个数,可以重复,有多少种组合是123,321,312,321,213,123是一种组合。比如输入3,3,有10种,分别为,111,112,113,122,123,133,222,223,233,333。输入4,2,有10种,分别为,11,22,33,44,12,13,23,...
  • ​​ 算出从n个不同元素中取出m个元素mn)的组合数。 建议定义和调用函数fact(n)计算n!,其中n的类型是int,函数类型是double。 输入格式: 输入在一行中给出两正整数mnmn),以空格分隔。 输出格式: ...
  • C++实现输出 n个不重复整数任取m个数的所有组合(附C语言实现) 一、简要说明 基本实现过程:先得到索引组合,再根据索引打印对应值。附C语言实现版。 二、效果图 三、例子说明 例如 64,声明一数组存储...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 133,672
精华内容 53,468
关键字:

n个元素取m个组合