Arrangement and combination algorithms are widely used and need to be mastered. In order to lower the threshold, this article mainly focuses on the logic and simplicity of the algorithm, but does not pay attention to algorithm efficiency. Combining the implementation in online books and their own needs, there are four goals here:
1. Full arrangement of all elements: The full arrangement of ab is ab, ba (order related);
2. Full combination of all elements: The full combination of ab is a, b, ab (order irrelevant);
3. Find out what are the combinations of selecting m elements among n elements: The combination of 2 elements in abc is ab, ac, bc;
4. Find out what are the arrangements for selecting m elements among n elements: The arrangements for selecting 2 elements in abc are ab, ba, ac, ca, bc, cb;
It can be found that after finding the arrangement of selecting m elements among n elements, we actually arrange the set of elements (arrays) composed of each combination after finding the combination method of selecting m elements among n elements, so it is a assembly function, and the examples are not listed. For the other three goals, see the code:
public final class PermutationCombinationHolder { /** Full combination of array elements*/ static void combination(char[] chars) { char[] subchars = new char[chars.length]; //Arrays that store subcombination data//The problem of the whole combination is to select 1 element from all elements (denoted as n), plus the combination of 2 elements... plus the sum of the combination of n elements for (int i = 0; i < chars.length; ++i) { final int m = i + 1; combination(chars, chars.length, m, subchars, m); } } /** * Implementation of the combination of n elements with n elements. The principle is as follows: * Select from behind to front, select position i, and then select m-1 in the first i-1. * For example: 3 elements are selected from 1, 2, 3, 4, 5. * 1) After selecting 5, then selecting 2 in the first 4, and selecting 2 in the first 4 is another sub-problem, just recursive; * 2) If you do not include 5, select 4 directly, then select 2 in the first 3, and selecting 2 in the first three is another sub-problem, just recursive; * 3) If you do not include 4, select 3 directly, then select 2 in the first 2, and there are only two in the first 2. * Looking at the vertical direction, 1 and 2 and 3 happen to be a for loop, the initial value is 5, and the final value is m. * Looking at the horizontal direction, this problem is a recursive of m-1 in the first i-1. */ static void combination(char[] chars, int n, int m, char[] subchars, int subn) { if (m == 0) { //Export for (int i = 0; i < subn; ++i) { System.out.print(subchars[i]); } System.out.println(); } else { for (int i = n; i >= m; --i) { //Select subchars[m - 1] = chars[i - 1]; //Select a combination(chars, i - 1, m - 1, subchars, subn); // Select m-1 from the first i-1 for recursion} } } } /** Full permutation of array elements*/ static void permutation(char[] chars) { permutation(chars, 0, chars.length - 1); } /** Subarrays in the array from index begin to index end participate in full permutation*/ static void permutation(char[] chars, int begin, int end) { if (begin == end) { //The exit is when only the last character is left 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 is fixed to the first if (canSwap(chars, begin, i)) { //Deduplicate swap(chars, begin, i); //Swap permutation(chars, begin + 1, end); //Recursively find the full permutation of the sub-array swap(chars, begin, i); //Restore} } } } } 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("====================================================== System.out.out.println(chars); }}The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.