【番外篇】排列组合实现算法2（Java版）

一、说明

在牛客网的很多算法试题中，很多试题底层都是基于排列组合算法实现的，比如最优解、最大值等常见问题。排列组合算法有一定的难度，并不能用一般的多重嵌套循环解决，没有提前做针对性的学习和研究，考试时候肯定是事倍功半，所以今天我们专门出一篇文章来讲一下这个问题。

排列个数的计算公式如下：

组合个数的计算公式如下：

二、放回再取问题

1、问题1：

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

分析：每一次取都有m种可能的情况，因此一共有种情况。

package xu.com.coder.test;import java.util.Stack;public class Recursion1Test {static Stack<Integer> stack = new Stack<Integer>();static int cnt = 0;public static void main(String[] args) {int[] data = {1, 2, 3, 4};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();}}}

运行结果：

 三、排列问题

问题2：        

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

分析：这是排列问题，应该有种情况。

package xu.com.coder.test;import java.util.Stack;public class Recursion2Test {static Stack<Integer> stack = new Stack<Integer>();static int cnt = 0;public static void main(String[] args) {int[] data = {1, 2, 3, 4};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();}}}}

运行结果：

四、组合问题

问题3：

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

分析：这是组合问题。因该有种可能性。

package xu.com.coder.test;import java.util.Stack;public class Recursion3Test {static Stack<Integer> stack = new Stack<Integer>();static int cnt = 0;public static void main(String[] args) {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();}}}}

 运行结果：