Java再帰的に文字列の全配列と全結合を実現する。


組み合わせアルゴリズムの用途が広く、把握する必要があります。敷居を下げるために、本論文では主にアルゴリズムの論理と簡易性に注目しています。アルゴリズムの効率を重視していません。ネットブックの実現と自分の需要を結び付けて、ここには四つの目標があります。
1.すべての要素の全配列:abの全配列はab、ba(順序関連)である。
2.すべての要素の全結合:a bの全結合は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個の要素を選択する組み合わせであり、各組み合わせからなる要素セット(配列)を完全に整列するため、スペル関数であり、例を列挙していない。他の3つの目標はコードを参照する。

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

以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。