从n个数中选取m个数的所有组合

蔚落 2023-02-15 10:03 17阅读 0赞

# 题目： #

![在这里插入图片描述][2020060421241697.png]

n个数1,2,...,n，从这n个数中任意选m个数，输出所有不同组合，共有C(n,m)种不同组合。
    
    如n=4，m=2，会产生如下输出：
    1 2 
    1 3 
    2 3 
    1 4 
    2 4 
    3 4
     
    如n=5，m=3，会产生如下输出：
    1 2 3 
    1 2 4 
    1 3 4 
    2 3 4 
    1 2 5 
    1 3 5 
    2 3 5 
    1 4 5 
    2 4 5 
    3 4 5

# 题解： #

## 1. 题解一：（正向打印） ##

1. 选择第i（m <=i<=n）个元素作为每个组合的最后元素，在第1————i个元素中往前（前i - 1个元素中）选取m-1个元素。
    2. 若m等于1（对应b[0]），则表示选完，输出该组合（数组b中存储的是组合的元素在a中的下标）
    3. 若m>1，则重复1、2步骤

例如：

从后往前选取，选定位置i后，再在前i-1个里面选取m-1个。
    
    如 1 2 3 4 5 中选取 3 个
    
    1、如果不包含5、也不包含4，直接选取3，那么再在前2个里面选取2个，刚好只有两个。
    
    2、如果只不包含5，直接选定4，那么再在前3个里面选取2个，而前3个里面选取2个又是一个子问题，递归即可。
    
    3、选取5后，再在前4个里面选取2个，而前4个里面选取2个又是一个子问题，递归即可。
    
    纵向看，1、2、3刚好是一个for循环，初值为m(m == 3)，终值为n(n == 5)
    
    横向看，该问题为一个前i-1个中选m-1的递归。

## 2. 题解二：（反向打印） ##

组合问题就是从n中选m个数，也是采用递归的方式

a. 首先从n个数中选取编号最大的数，然后在剩下的n-1个数里面选取m-1个数，直到从n-(m-1)个数中选取1个数为止。

b. 从n个数中选取编号次小的一个数，继续执行1步，直到当前可选编号最大的数为m。

# 代码： #

## 1. 代码一：（正向打印） ##

import java.util.*;
    
    public class Main { 
    
        public static void C(int n, int m, int a[], int b[])
        { 
            for(int i = m; i <= n; i++)
            { 
                b[m - 1] = i - 1;
                if(m > 1)
                { 
                    C(i - 1, m - 1, a, b);
                }
                else
                { 
                    for(int j = 0; j < b.length; j++)
                    { 
                        System.out.printf("%d ", a[b[j]]);
                    }
                    System.out.println();
                }
            }
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(); // 4
            int m = sc.nextInt(); // 2
            int a[] = new int[n];
            for(int i = 0; i < n; i++)
            { 
                a[i] = i + 1; // a[0, 1, 2, 3] = { 1, 2, 3, 4};
            }
            int b[] = new int[m]; // 数组b中存储的是组合的元素在a中的下标
            C(n, m, a, b);
            sc.close();
        }
        
    }
    
    // // 输入：
    // 4 2
    
    // // 输出：
    // 12
    // 13
    // 23
    // 14
    // 24
    // 34

## 2. 代码二：（反向打印） ##

/// 求从数组a[1..n]中任选m个元素的所有组合。
    /// a[1..n]表示候选集，n为候选集大小，n>=m>0。
    /// b[1..M]用来存储当前组合中的元素(这里存储的是元素下标)，
    /// 常量M表示满足条件的一个组合中元素的个数，M=m，这两个参数仅用来输出结果。
    void combine( int a[], int n, int m,  int b[], const int M )
    { 
      for(int i=n; i>=m; i--)   // 注意这里的循环范围
      { 
         b[m-1] = i - 1;
         if (m > 1)
           combine(a,i-1,m-1,b,M);
         else                     // m == 1, 输出一个组合
         { 
           for(int j=M-1; j>=0; j--)
           cout << a[b[j]] << " ";
           cout << endl;
         }
      }
    }

# 参考： #

1.  [（剑指offer）从n个数中选取m个数的所有组合][offer_n_m]
2.  [打印从n个数种选取m个数的组合数][n_m]
3.  [排列组合算法][Link 1]
4.  [C语言实现的排列组合问题的通用算法、解决方法][C]
5.  [输出从n个数中选m个数的所有组合][n_m 1]
6.  [递归实现 从n个数中选取m个数的所有组合][_n_m]

[2020060421241697.png]: https://img-blog.csdnimg.cn/2020060421241697.png
[offer_n_m]: https://blog.csdn.net/JAck_chen0309/article/details/105675428
[n_m]: https://www.cnblogs.com/GlassHour/p/5784273.html
[Link 1]: https://www.cnblogs.com/xkfz007/archive/2012/06/02/2531996.html
[C]: https://www.xp.cn/b.php/102962.html
[n_m 1]: https://blog.csdn.net/life_liver/article/details/12624483
[_n_m]: https://blog.csdn.net/shaoxiaohu1/article/details/50684782