排列组合的模板算法

排列组合（百度百科）

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。

举例说明

//abc的排列
abc  acb  bac  bca  cba  cab
共有6种排序

//abc的组合
3取3的可能：abc
3取2的可能：ab  ac  bc
3取1的可能：a  b  c

排列模板代码

/**
 * @author god-jiang
 * @date 2020/3/23  14:31
 */
public class Permutation {
    //全排列
    public static void perm(char[] arr, int start, int len) {
        if (start == len - 1) {
            for (int i = 0; i < len; i++) {
                System.out.print(arr[i]);
            }
            System.out.println();
        } else {
            for (int i = start; i < len; i++) {
                swap(arr, start, i);
                perm(arr, start + 1, len);
                swap(arr, start, i);
            }
        }
    }

    //交换两个数
    public static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        char[] arr = "abc".toCharArray();
        perm(arr, 0, arr.length);
    }
}

---

组合模板代码

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/3/23  14:57
 */
public class Combination {
    public static void dfs(char[] input, char[] output, int index, int start) {
        if (index == output.length) {
            System.out.println(Arrays.toString(output));
        } else {
            for (int j = start; j < input.length; j++) {
                output[index] = input[j];
                dfs(input, output, index + 1, j + 1);
            }
        }
    }

    public static void main(String[] args) {
        char[] input = "abc".toCharArray();
        //N表示组合中取几位数
        int N = 2;
        char[] output = new char[N];
        dfs(input, output, 0, 0);
    }
}

PS：一般比赛或者笔试都可以直接当作模板来使用。就好比，蓝桥杯比赛和牛客网笔试要带输入输出模板一样。然后就是希望对你们有所帮助。