Java遞歸實(shí)現(xiàn)字符串全排列與全組合

public final class PermutationCombinationHolder {

  /** 數(shù)組元素的全組合 */
  static void combination(char[] chars) {
    char[] subchars = new char[chars.length]; //存儲子組合數(shù)據(jù)的數(shù)組
    //全組合問題就是所有元素(記為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個元素的組合問題的實(shí)現(xiàn). 原理如下:
   * 從后往前選取, 選定位置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循環(huán), 初值為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個進(jìn)行遞歸
      }
    }
  }

  /** 數(shù)組元素的全排列 */
  static void permutation(char[] chars) {
    permutation(chars, 0, chars.length - 1);
  }

  /** 數(shù)組中從索引begin到索引end之間的子數(shù)組參與到全排列 */
  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) { //每個字符依次固定到數(shù)組或子數(shù)組的第一個
        if (canSwap(chars, begin, i)) { //去重
          swap(chars, begin, i); //交換
          permutation(chars, begin + 1, end); //遞歸求子數(shù)組的全排列
          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);
  }
}