实现排列与组合

排列

用程序实现排列可以说是暴力求解的基础,也可以说是DFS.

说一下简单的思路:

• 首先排列就是把一列数按照不同的顺序列出来.所以根据这个要求我们知道,每个数在一种排列中只能使用一次,我们需要想办法把已经使用的数标记出来防止它重复使用.
• 然后,实现若干个数排列怎么实现若干个数的循环访问?用for循环肯定是不行的,所以我们一般使用递归.

排列的简单实现(n=10以上谨慎使用,不加入剪枝的话,11左右就是一般OJ题的运行极限了)

import java.util.Arrays;

public class DFS01 {


    static int n = 8;//0-n的排列
    static int[] ans = new int[n];
    static boolean[] flag = new boolean[n];

    public static void main(String[] args) {
        dfs(0);

    }

    static void dfs(int lie) {
        if (lie == n) {
            System.out.println(Arrays.toString(ans));
        }
        for (int i = 0; i < n; i++) {
            if (!flag[i]) {//如果这个数没有被标记
                flag[i] = true;//标记这个数
                ans[lie] = i;//把这个数加入最终答案
                dfs(lie + 1);//递归调用
                flag[i] = false;//把这个数取消标记
            }
        }

    }

}

组合

首先说一下组合,大致就是在一个有n个球的袋子里摸出m个球,有集中情况出现?

和排列区别是排列区分顺序,组合不区分顺序.

思路很简单,只需要想清楚怎么实现选和不选就可以了.

import java.util.Arrays;

public class DFS02 {


    static int n = 10;//一共有n个球
    static int m = 4;//摸出m个
    static int[] ans = new int[n];

    public static void main(String[] args) {
        dfs(0, 0);
    }
    
    /**
     * @param num 当前的编号
     * @param lie 当前摸的是第几个球
     */
    static void dfs(int num, int lie) {
        if (num > n) {//编号大于n,没有这个球
            return;
        }
        if (lie == m) {//已经摸出了m个球
            System.out.println(Arrays.toString(Arrays.copyOf(ans, m)));
            return;
        }
        ans[lie] = num;//第lie次摸出了编号为num的球
        dfs(num + 1, lie + 1);//选球
        dfs(num + 1, lie);//不选球

    }

}

实现排列与组合

原文：https://www.cnblogs.com/continued258/p/12500789.html