Java recursive string full arrangement and full combination

  • 2021-01-19 22:16:13
  • OfStack

Permutation and combination algorithm is widely used and needs to be mastered. In order to reduce the threshold, this paper mainly focuses on the logic and simplicity of the algorithm, but does not pay attention to the efficiency of the algorithm. Combined with the implementation of the online book and your own needs, here are four goals listed:

1. The full permutation of all elements: the full permutation of ab is ab, ba(sequentially related);
2. Full combination of all elements: The full combination of ab is a, b, ab(sequentially independent);
3. Find the combinations of m elements in n: the combinations of 2 elements in abc are ab, ac, bc;
4. Find the permutations of m elements in n: 2 elements in abc are ab, ba, ac, ca, bc, cb;

It can be found that the arrangement method of selecting m elements from n elements is actually a complete arrangement of the element set (array) composed of each combination after the combination method of selecting m elements from n elements is worked out. Therefore, it is an assembly function without examples listed. The other three targets are shown in the code:


public final class PermutationCombinationHolder {

  /**  A full combination of array elements  */
  static void combination(char[] chars) {
    char[] subchars = new char[chars.length]; // An array to store subcombined data 
    // The total combination problem is all the elements ( Remember to n) select 1 A combination of three elements ,  Combined with selected 2 A combination of three elements ... Combined with selected n The sum of a combination of three elements 
    for (int i = 0; i < chars.length; ++i) {
      final int m = i + 1;
      combination(chars, chars.length, m, subchars, m);
    }
  }

  /**
   * n Element to choose m The realization of a combination of elements .  Principle is as follows :
   *  Selecting from the back to the front ,  The selected location i after ,  In the former again i-1 Select from inside m-1 a .
   *  Such as : 1, 2, 3, 4, 5  Select the 3 An element .
   * 1)  select 5 after ,  In the former again 4 Select from inside 2 a ,  The former 4 Select from inside 2 another 1 Is the problem ,  Recursion can ;
   * 2)  If it doesn't include 5,  Directly selected 4,  So first 3 Select from inside 2 a ,  The former 3 Select from inside 2 another 1 Is the problem ,  Recursion can ;
   * 3)  If it doesn't 4,  Direct selection 3,  So first 2 Select from inside 2 a ,  There just happened to be two .
   *  Longitudinal see , 1 with 2 with 3 just 1 a for cycle ,  Initial value for the 5,  Final value for m.
   *  Lateral see ,  The problem is 1 A former i-1 A selected m-1 The recursive .
   */
  static void combination(char[] chars, int n, int m, char[] subchars, int subn) {
    if (m == 0) { // exit 
      for (int i = 0; i < subn; ++i) {
        System.out.print(subchars[i]);
      }
      System.out.println();
    } else {
      for (int i = n; i >= m; --i) { //  Select from back to front 1 a 
        subchars[m - 1] = chars[i - 1]; //  The selected 1 After a 
        combination(chars, i - 1, m - 1, subchars, subn); //  Once upon a time i-1 Select from inside m-1 I'm going to recurse 
      }
    }
  }

  /**  The full arrangement of the elements of an array  */
  static void permutation(char[] chars) {
    permutation(chars, 0, chars.length - 1);
  }

  /**  Array from the index begin To the index end Between the subarrays involved in the full permutation  */
  static void permutation(char[] chars, int begin, int end) {
    if (begin == end) { // Only the last 1 Is an exit 
      for (int i = 0; i < chars.length; ++i) {
        System.out.print(chars[i]);
      }
      System.out.println();
    } else {
      for (int i = begin; i <= end; ++i) { // Each character, in turn, is pinned to the first of an array or subarray 1 a 
        if (canSwap(chars, begin, i)) { // duplicate removal 
          swap(chars, begin, i); // exchange 
          permutation(chars, begin + 1, end); // Find the full array of subarrays recursively 
          swap(chars, begin, i); // reduction 
        }
      }
    }
  }

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


Related articles: