Java递归实现字符串全排列与全组合
排列组合算法用途广泛,需要掌握,为降低门槛,本文主要关注算法的逻辑和简易性,未重视算法效率. 结合网络书本上的实现和自己的需求,这里列有四个目标:
1. 所有元素的全排列: ab的全排列是ab, ba(顺序相关);
2. 所有元素的全组合: ab的全组合是a, b, ab(顺序无关);
3. 求n个元素中选取m个元素的组合方式有哪些: abc中选2个元素的组合是ab, ac, bc;
4. 求n个元素中选取m个元素的排列方式有哪些: abc中选2个元素的排列是ab, ba, ac, ca, bc, cb;
可以发现,求n个元素中选取m个元素的排列方式其实是在求出n个元素中选取m个元素的组合方式后,对每个组合组成的元素集(数组)做全排列,所以它是一个拼装函数,未列出示例,其他三个目标,看代码:
public final class PermutationCombinationHolder { /** 数组元素的全组合 */ static void combination(char[] chars) { char[] subchars = new char[chars.length]; //存储子组合数据的数组 //全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加上选n个元素的组合的和 for (int i = 0; i < chars.length; ++i) { final int m = i + 1; combination(chars, chars.length, m, subchars, m); } } /** * n个元素选m个元素的组合问题的实现. 原理如下: * 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个. * 如: 1, 2, 3, 4, 5 中选取3个元素. * 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可; * 2) 如果不包含5, 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可; * 3) 如果也不包含4, 直接选取3, 那么再在前2个里面选取2个, 刚好只有两个. * 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m. * 横向看, 该问题为一个前i-1个中选m-1的递归. */ static void combination(char[] chars, int n, int m, char[] subchars, int subn) { if (m == 0) { //出口 for (int i = 0; i < subn; ++i) { System.out.print(subchars[i]); } System.out.println(); } else { for (int i = n; i >= m; --i) { // 从后往前依次选定一个 subchars[m - 1] = chars[i - 1]; // 选定一个后 combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归 } } } /** 数组元素的全排列 */ static void permutation(char[] chars) { permutation(chars, 0, chars.length - 1); } /** 数组中从索引begin到索引end之间的子数组参与到全排列 */ static void permutation(char[] chars, int begin, int end) { if (begin == end) { //只剩最后一个字符时为出口 for (int i = 0; i < chars.length; ++i) { System.out.print(chars[i]); } System.out.println(); } else { for (int i = begin; i <= end; ++i) { //每个字符依次固定到数组或子数组的第一个 if (canSwap(chars, begin, i)) { //去重 swap(chars, begin, i); //交换 permutation(chars, begin + 1, end); //递归求子数组的全排列 swap(chars, begin, i); //还原 } } } } static void swap(char[] chars, int from, int to) { char temp = chars[from]; chars[from] = chars[to]; chars[to] = temp; } static boolean canSwap(char[] chars, int begin, int end) { for (int i = begin; i < end; ++i) { if (chars[i] == chars[end]) { return false; } } return true; } public static void main(String[] args) { final char[] chars = new char[] {'a', 'b', 'c'}; permutation(chars); System.out.println("==================="); combination(chars); } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
您可能感兴趣的文章:
- java字符串与日期类型转换的工具类
- java实现时间与字符串之间转换
- Java实现去掉字符串重复字母的方法示例
- Java编程实现对十六进制字符串异或运算代码示例
- java中拼接字符串的5种方法效率对比
- java实现图片转base64字符串 java实现base64字符串转图片
- Java实现abc字符串排列组合
- java实现字符串排列组合问题
- Java排列组合字符串的方法
- java实现字符串的全排列
- Java中BufferedReader类获取输入输入字符串实例
- Java字符串查找的三种方式
赞 (0)