java实现排列组合

朴灿烈づ我的快乐病毒、 2022-12-21 14:58 110阅读 0赞

# 数学问题 - java实现排列组合 #

--------------------

今天遇到一个组合问题，整理学习相关数学算法问题，并做记录。

如果和我一样已经忘记数学集合，排列组合问题的，就需要先看下排列组合推导，及公式。

排列公式：A(n,m)=n!/(n-m)!

组合公式：C(n,m)=n!/m!(n-m)!

二项式定理：非空子集=2^n -1

--------------------

**目录**

数学问题 - java实现排列组合

一、放回再取问题

二、排列问题

三、组合问题

总结：

--------------------

## 一、放回再取问题 ##

**问题1：**

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

分析：

每一次取都有m种可能的情况，因此一共有![gif.latex_5Cinline_20m_5En][]种情况。

//    问题1：
    //    假设袋子里有编号为1,2,...,m这m个球。现在每次从袋子中取一个球几下编号，放回袋中再取，取n次作为一组，枚举所有可能的情况。
    //
    //    分析：
    //    每一次取都有m种可能的情况，因此一共有种情况。
    
        //看第一个问题, 有1,2,3,4这4个数字.可以重复的在里面选3次,问能得到多少种结果
        //栈 先进后出，数组的数据模型
        static Stack<Integer> stack = new Stack<Integer>();
        static int cnt = 0;
    
        @Test
        public void testRecursion() {
            int[] data = {1, 2, 3};
            recursion(data, 0, 3);
            System.out.println(cnt);
        }
    
        /**
         * 递归方法，当实际选取的数目与要求选取的小目相同时，跳出递归
         *
         * @param array  - 数组
         * @param curnum - 当前已经确定的个数
         * @param maxnum - 要选取的数目
         */
        public static void recursion(int[] array, int curnum, int maxnum) {
            if (curnum == maxnum) {
                cnt++;
                System.out.println(stack);
                return;
            }
            for (int item : array) {
                stack.push(item);
                recursion(array, curnum + 1, maxnum);
                stack.pop();
            }
        }

打印结果

\[1, 1, 1\]  
\[1, 1, 2\]  
\[1, 1, 3\]  
\[1, 2, 1\]  
\[1, 2, 2\]  
\[1, 2, 3\]  
\[1, 3, 1\]  
\[1, 3, 2\]  
\[1, 3, 3\]  
\[2, 1, 1\]  
\[2, 1, 2\]  
\[2, 1, 3\]  
\[2, 2, 1\]  
\[2, 2, 2\]  
\[2, 2, 3\]  
\[2, 3, 1\]  
\[2, 3, 2\]  
\[2, 3, 3\]  
\[3, 1, 1\]  
\[3, 1, 2\]  
\[3, 1, 3\]  
\[3, 2, 1\]  
\[3, 2, 2\]  
\[3, 2, 3\]  
\[3, 3, 1\]  
\[3, 3, 2\]  
\[3, 3, 3\]  
27

--------------------

## 二、排列问题 ##

问题2：

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

分析：

这是排列问题，应该有![gif.latex_5Cinline_20A_7Bm_7D_5E_7Bn_7D][]种情况。

//    问题2：
    //    假设袋子里有编号为1,2,...,m这m个球。先后从袋子中取出n个球，依次记录编号，枚举所有可能的情况。
    
        static Stack<Integer> stack = new Stack<Integer>();
        static int cnt = 0;
    
        @Test
        public void testRecursion2() {
            int[] data = {1, 2, 3};
            recursion2(data, 0, 3);
            System.out.println(cnt);
        }
    
        public static void recursion2(int[] array, int curnum, int maxnum) {
            if (curnum == maxnum) {
                cnt++;
                System.out.println(stack);
                return;
            }
            for (int item : array) {
                if (!stack.contains(item)) {
                    stack.push(item);
                    recursion2(array, curnum + 1, maxnum);
                    stack.pop();
                }
            }
        }

打印结果：

\[1, 2, 3\]  
\[1, 3, 2\]  
\[2, 1, 3\]  
\[2, 3, 1\]  
\[3, 1, 2\]  
\[3, 2, 1\]  
6

--------------------

## 三、组合问题 ##

问题3：

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

分析：

这是组合问题。因该有![gif.latex_C_7Bm_7D_5E_7Bn_7D][]种可能性。

//    问题3：
    //    从m个球里（编号为1,2,3...,m）一次取n个球，其中m>n，记录取出球的编号，枚举所有的可能性
        
        static Stack<Integer> stack = new Stack<Integer>();
        static int cnt = 0;
        
        @Test
        public void testRecursion3() {
            int[] data = {1, 2, 3, 4};
            recursion3(data, 0, 3, 0);
            System.out.println(cnt);
        }
        
        public static void recursion3(int[] array, int curnum, int maxnum, int indexnum) {
            if (curnum == maxnum) {
                cnt++;
                System.out.println(stack);
                return;
            }
            for (int i = indexnum; i < array.length; i++) {
                if (!stack.contains(array[i])) {
                    stack.push(array[i]);
                    recursion3(array, curnum + 1, maxnum, i);
                    stack.pop();
                }
            }
        }

打印结果：

\[1, 2, 3\]  
\[1, 2, 4\]  
\[1, 3, 4\]  
\[2, 3, 4\]  
4

--------------------

# 总结： #

1、数学问题，排列组合

2、递归思想

3、巧妙的运用了栈stack

--------------------

[java中的栈stack][java_stack]  [https://blog.csdn.net/xinpz/article/details/109642137][https_blog.csdn.net_xinpz_article_details_109642137]

--------------------

参考：

[https://www.cnblogs.com/zzlback/p/10947064.html][https_www.cnblogs.com_zzlback_p_10947064.html]

[https://blog.csdn.net/Ring\_k/article/details/79575533][https_blog.csdn.net_Ring_k_article_details_79575533]

[gif.latex_5Cinline_20m_5En]: /images/20221120/d870acda477b48f784bfb05bbc03f824.png
[gif.latex_5Cinline_20A_7Bm_7D_5E_7Bn_7D]: /images/20221120/478137baf6864f96a4ee03187d713dd1.png
[gif.latex_C_7Bm_7D_5E_7Bn_7D]: http://latex.codecogs.com/gif.latex?C_%7Bm%7D%5E%7Bn%7D
[java_stack]: https://mp.csdn.net/console/editor/html/109642137
[https_blog.csdn.net_xinpz_article_details_109642137]: https://blog.csdn.net/xinpz/article/details/109642137
[https_www.cnblogs.com_zzlback_p_10947064.html]: https://www.cnblogs.com/zzlback/p/10947064.html
[https_blog.csdn.net_Ring_k_article_details_79575533]: https://blog.csdn.net/Ring_k/article/details/79575533