【算法笔记】深度优先遍历-解决排列组合问题-

古城微笑少年丶 2024-03-23 18:56 5阅读 0赞

## 深度优先遍历-解决排列组合问题 ##

### 问题1： ###

> 假设袋子里有编号为1,2,…,m这m个球。现在每次从袋子中取一个球记下编号，放回袋中再取，取n次作为一组，枚举所有可能的情况。

**分析：**  
每一次取都有m种可能的情况，因此一共有 m n m^n mn种情况。  
这里我们取m = 3, n = 4，则有 3 4 3^4 34种不同的情况。

**代码：**

import java.util.Stack;
     
    public class Test {
        
        static int cnt = 0;
        static Stack<Integer> s = new Stack<Integer>();
     
        /**
         * 递归方法，当实际选取的小球数目与要求选取的小球数目相同时，跳出递归
         * @param minv - 小球编号的最小值
         * @param maxv - 小球编号的最大值
         * @param curnum - 当前已经确定的小球的个数
         * @param maxnum - 要选取的小球的数目
         */
        public static void kase1(int minv,int maxv,int curnum, int maxnum){
        
            if(curnum == maxnum){
        
                cnt++;
                System.out.println(s);
                return;
            }
     
            for(int i = minv; i <= maxv; i++){
        
                s.push(i);
                kase1(minv, maxv, curnum+1, maxnum);
                s.pop();
            }
        }
     
        public static void main(String[] args){
        
            kase1(1, 3, 0, 4);
            System.out.println(cnt);
        }
    }

输出：

[1, 1, 1, 1]
    [1, 1, 1, 2]
    [1, 1, 1, 3]
    [1, 1, 2, 1]
    [1, 1, 2, 2]
    [1, 1, 2, 3]
    [1, 1, 3, 1]
    [1, 1, 3, 2]
    [1, 1, 3, 3]
    [1, 2, 1, 1]
    [1, 2, 1, 2]
    [1, 2, 1, 3]
    [1, 2, 2, 1]
    [1, 2, 2, 2]
    [1, 2, 2, 3]
    [1, 2, 3, 1]
    [1, 2, 3, 2]
    [1, 2, 3, 3]
    [1, 3, 1, 1]
    [1, 3, 1, 2]
    [1, 3, 1, 3]
    [1, 3, 2, 1]
    [1, 3, 2, 2]
    [1, 3, 2, 3]
    [1, 3, 3, 1]
    [1, 3, 3, 2]
    [1, 3, 3, 3]
    [2, 1, 1, 1]
    [2, 1, 1, 2]
    [2, 1, 1, 3]
    [2, 1, 2, 1]
    [2, 1, 2, 2]
    [2, 1, 2, 3]
    [2, 1, 3, 1]
    [2, 1, 3, 2]
    [2, 1, 3, 3]
    [2, 2, 1, 1]
    [2, 2, 1, 2]
    [2, 2, 1, 3]
    [2, 2, 2, 1]
    [2, 2, 2, 2]
    [2, 2, 2, 3]
    [2, 2, 3, 1]
    [2, 2, 3, 2]
    [2, 2, 3, 3]
    [2, 3, 1, 1]
    [2, 3, 1, 2]
    [2, 3, 1, 3]
    [2, 3, 2, 1]
    [2, 3, 2, 2]
    [2, 3, 2, 3]
    [2, 3, 3, 1]
    [2, 3, 3, 2]
    [2, 3, 3, 3]
    [3, 1, 1, 1]
    [3, 1, 1, 2]
    [3, 1, 1, 3]
    [3, 1, 2, 1]
    [3, 1, 2, 2]
    [3, 1, 2, 3]
    [3, 1, 3, 1]
    [3, 1, 3, 2]
    [3, 1, 3, 3]
    [3, 2, 1, 1]
    [3, 2, 1, 2]
    [3, 2, 1, 3]
    [3, 2, 2, 1]
    [3, 2, 2, 2]
    [3, 2, 2, 3]
    [3, 2, 3, 1]
    [3, 2, 3, 2]
    [3, 2, 3, 3]
    [3, 3, 1, 1]
    [3, 3, 1, 2]
    [3, 3, 1, 3]
    [3, 3, 2, 1]
    [3, 3, 2, 2]
    [3, 3, 2, 3]
    [3, 3, 3, 1]
    [3, 3, 3, 2]
    [3, 3, 3, 3]
    81

### 问题2： ###

> 假设袋子里有编号为1,2,…,m这m个球。先后从袋子中取出n个球，依次记录编号，枚举所有可能的情况。

**分析：**  
这是排列问题，如果取出的球顺序不同，也是算不同的情况。因此应该有 m ∗ ( m − 1 ) ∗ ( m − 2 ) ∗ . . . ∗ ( m − n + 1 ) m\*(m-1)\*(m-2)\*...\*(m-n+1) m∗(m−1)∗(m−2)∗...∗(m−n\+1)种情况，即 A m n = m ! ( m − n ) ! A\_m^n=\\frac\{m!\}\{(m-n)!\} Amn=(m−n)!m!种  
这里取m = 5, n = 3。则有`5*4*3`种。  
和问题1相比，唯一的区别是排列中不可以有重复。因此开了used数组用以标记是否已经访问。

**代码：**

import java.util.Stack;
     
    public class Test {
        
        static int cnt = 0;
        static Stack<Integer> s = new Stack<Integer>();
        static boolean[] used = new boolean[10000];
     
        /**
         * 递归方法，当实际选取的小球数目与要求选取的小球数目相同时，跳出递归
         * @param minv - 小球编号的最小值
         * @param maxv - 小球编号的最大值
         * @param curnum - 当前已经确定的小球的个数
         * @param maxnum - 要选取的小球的数目
         */
        public static void kase2(int minv,int maxv,int curnum, int maxnum){
        
            if(curnum == maxnum){
        
                cnt++;
                System.out.println(s);
                return;
            }
     
            for(int i = minv; i <= maxv; i++){
        
                if(!used[i]){
         //判断是否已经取过
                    s.push(i);
                    used[i] = true;
                    kase2(minv, maxv, curnum+1, maxnum);
                    s.pop();
                    used[i] = false;
                }
            }
        }
     
        public static void main(String[] args){
        
            kase2(1, 5, 0, 3);
            System.out.println(cnt);
        }
    }

输出：

[1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 3, 2]
    [1, 3, 4]
    [1, 3, 5]
    [1, 4, 2]
    [1, 4, 3]
    [1, 4, 5]
    [1, 5, 2]
    [1, 5, 3]
    [1, 5, 4]
    [2, 1, 3]
    [2, 1, 4]
    [2, 1, 5]
    [2, 3, 1]
    [2, 3, 4]
    [2, 3, 5]
    [2, 4, 1]
    [2, 4, 3]
    [2, 4, 5]
    [2, 5, 1]
    [2, 5, 3]
    [2, 5, 4]
    [3, 1, 2]
    [3, 1, 4]
    [3, 1, 5]
    [3, 2, 1]
    [3, 2, 4]
    [3, 2, 5]
    [3, 4, 1]
    [3, 4, 2]
    [3, 4, 5]
    [3, 5, 1]
    [3, 5, 2]
    [3, 5, 4]
    [4, 1, 2]
    [4, 1, 3]
    [4, 1, 5]
    [4, 2, 1]
    [4, 2, 3]
    [4, 2, 5]
    [4, 3, 1]
    [4, 3, 2]
    [4, 3, 5]
    [4, 5, 1]
    [4, 5, 2]
    [4, 5, 3]
    [5, 1, 2]
    [5, 1, 3]
    [5, 1, 4]
    [5, 2, 1]
    [5, 2, 3]
    [5, 2, 4]
    [5, 3, 1]
    [5, 3, 2]
    [5, 3, 4]
    [5, 4, 1]
    [5, 4, 2]
    [5, 4, 3]
    60

### 问题3： ###

> 从m个球里（编号为1,2,3…,m）一次取n个球，其中m>n，记录取出球的编号，枚举所有的可能性。

分析：  
这是组合问题。应该有 ( m n ) = m ! n ! ( m − n ) ! \\binom\{m\}\{n\}=\\frac\{m!\}\{n!(m-n)!\} (nm)=n!(m−n)!m!种可能性。  
这里，如果取m = 8, n = 4. 则有 ( 8 4 ) = 8 ! 4 ! ( 8 − 4 ) ! = 8 × 7 × 6 × 5 4 × 3 × 2 × 1 = 70 \\binom\{8\}\{4\}=\\frac\{8!\}\{4!(8-4)!\}=\\frac\{8\\times7\\times6\\times5\}\{4\\times3\\times2\\times1\}=70 (48)=4!(8−4)!8!=4×3×2×18×7×6×5=70种可能。

代码：

import java.util.Stack;
     
    public class Test {
        
        static int cnt = 0;
        static Stack<Integer> s = new Stack<Integer>();
     
        /**
         * 递归方法，当前已抽取的小球个数与要求抽取小球个数相同时，退出递归
         * @param curnum - 当前已经抓取的小球数目
         * @param curmaxv - 当前已经抓取小球中最大的编号
         * @param maxnum - 需要抓取小球的数目
         * @param maxv - 待抓取小球中最大的编号
         */
        public static void kase3(int curnum, int curmaxv,  int maxnum, int maxv){
        
            if(curnum == maxnum){
        
                cnt++;
                System.out.println(s);
                return;
            }
     
            for(int i = curmaxv + 1; i <= maxv; i++){
         // i <= maxv - maxnum + curnum + 1
                s.push(i);
                kase3(curnum + 1, i, maxnum, maxv);
                s.pop();
            }
        }
     
        public static void main(String[] args){
        
            kase3(0, 0, 4, 8);
            System.out.println(cnt);
        }
    }

输出：

[1, 2, 3, 4]
    [1, 2, 3, 5]
    [1, 2, 3, 6]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 4, 5]
    [1, 2, 4, 6]
    [1, 2, 4, 7]
    [1, 2, 4, 8]
    [1, 2, 5, 6]
    [1, 2, 5, 7]
    [1, 2, 5, 8]
    [1, 2, 6, 7]
    [1, 2, 6, 8]
    [1, 2, 7, 8]
    [1, 3, 4, 5]
    [1, 3, 4, 6]
    [1, 3, 4, 7]
    [1, 3, 4, 8]
    [1, 3, 5, 6]
    [1, 3, 5, 7]
    [1, 3, 5, 8]
    [1, 3, 6, 7]
    [1, 3, 6, 8]
    [1, 3, 7, 8]
    [1, 4, 5, 6]
    [1, 4, 5, 7]
    [1, 4, 5, 8]
    [1, 4, 6, 7]
    [1, 4, 6, 8]
    [1, 4, 7, 8]
    [1, 5, 6, 7]
    [1, 5, 6, 8]
    [1, 5, 7, 8]
    [1, 6, 7, 8]
    [2, 3, 4, 5]
    [2, 3, 4, 6]
    [2, 3, 4, 7]
    [2, 3, 4, 8]
    [2, 3, 5, 6]
    [2, 3, 5, 7]
    [2, 3, 5, 8]
    [2, 3, 6, 7]
    [2, 3, 6, 8]
    [2, 3, 7, 8]
    [2, 4, 5, 6]
    [2, 4, 5, 7]
    [2, 4, 5, 8]
    [2, 4, 6, 7]
    [2, 4, 6, 8]
    [2, 4, 7, 8]
    [2, 5, 6, 7]
    [2, 5, 6, 8]
    [2, 5, 7, 8]
    [2, 6, 7, 8]
    [3, 4, 5, 6]
    [3, 4, 5, 7]
    [3, 4, 5, 8]
    [3, 4, 6, 7]
    [3, 4, 6, 8]
    [3, 4, 7, 8]
    [3, 5, 6, 7]
    [3, 5, 6, 8]
    [3, 5, 7, 8]
    [3, 6, 7, 8]
    [4, 5, 6, 7]
    [4, 5, 6, 8]
    [4, 5, 7, 8]
    [4, 6, 7, 8]
    [5, 6, 7, 8]
    70