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);
    }
  }

  
  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);
  }

  
  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);
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。