排列组合算法（Java）

心已赠人 2022-06-09 06:49 328阅读 0赞

网上搜排列组合算法，搜索结果一堆，但极少能说清楚排列和组合的区别，算法也糊里糊涂糊弄人的居多。因为工作中有一个逻辑需要用到组合算法，花了小半天时间弄好了，记录在这里供有需要的人使用。

### 先看定义 ###

排列组合：permutation and combination

combination组合，表示字母为C，是无序的；从n个不同的元素中取出m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合，表示为C(n,m)

permutation排列，表示字母为A，是有序的；从n个不痛的元素中取出m个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列，表示为A(n,m)

重点：排列有序，组合无序。

例子：略，后补

### 组合 ###

import java.util.ArrayList;
    
    /** * 组合 * * Created by majl on 2017/8/28. */
    public class CombinationUtil { 
    
        public static void main(String[] args) {
            ArrayList<String> is = new ArrayList<String>();
            is.add("1");
            is.add("2");
            is.add("3");
            is.add("4");
            ArrayList<String> res = new CombinationUtil().combine(is, "", 2);
            for (String str : res) {
                System.out.println(str);
            }
        }
    
        public static ArrayList<String> combine(ArrayList<String> is, String s, int m) {
            ArrayList<String> res = new ArrayList<String>();
            if (m == 0) {
                res.add(s);
                return res;
            }
            for (int i = 0; i < is.size(); i++) {
                String str = "";
                if (s.equals("")) {
                    str = is.get(i);
                } else {
                    str = s + "," + is.get(i);
                }
                ArrayList<String> innerIs = new ArrayList<String>();
                for (int j = i + 1; j < is.size(); j++) {
                    innerIs.add(is.get(j));
                }
                ArrayList<String> innerRes = combine(innerIs, str, m - 1);
                res.addAll(innerRes);
            }
            return res;
        }
    }

运行结果：

1,2
    1,3
    1,4
    2,3
    2,4
    3,4

### 排列 ###

import java.util.ArrayList;
    
    /** * 排列 * * Created by majl on 2017/8/28. */
    public class PermutationUtil { 
        public static void main(String[] args) {
            ArrayList<String> is = new ArrayList<String>();
            is.add("1");
            is.add("2");
            is.add("3");
            is.add("4");
            ArrayList<String> res = new PermutationUtil().permutate(is, "", 2);
            for (String str : res) {
                System.out.println(str);
            }
        }
    
        public static ArrayList<String> permutate(ArrayList<String> is, String s, int m) {
            ArrayList<String> res = new ArrayList<String>();
            if (m == 0) {
                res.add(s);
                return res;
            }
            for (int i = 0; i < is.size(); i++) {
                String str = "";
                if (s.equals("")) {
                    str = is.get(i);
                } else {
                    str = s + "," + is.get(i);
                }
                ArrayList<String> innerIs = new ArrayList<String>();
                innerIs.addAll(is);
                innerIs.remove(i);
                ArrayList<String> innerRes = permutate(innerIs, str, m - 1);
                res.addAll(innerRes);
            }
            return res;
        }
    }

运行结果：

1,2
    1,3
    1,4
    2,1
    2,3
    2,4
    3,1
    3,2
    3,4
    4,1
    4,2
    4,3

--------------------

对比一下运行结果，可以看到排列是包含了组合在里面的。

如果有时间的话，我会把例子和代码逻辑解释补齐。