Java排列组合算法

本算法场景在优惠券组合计算上，通过用户持有优惠券、计算出优惠券可用叠加的组合。算法已经抽象为通用的排列组合，拿下标计算。

排列组合算法

本算法场景在优惠券组合计算上，通过用户持有优惠券、计算出优惠券可用叠加的组合。算法已经抽象为通用的排列组合，拿下标计算。

代码如下

package com.yamibuy.mkt.service.common.coupon;

import cn.hutool.core.collection.CollectionUtil;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 优惠券组合数计算
 */
public class CouponCombSolution {

    /**
     * 参与组合的集合
     */
    private List<String> element;

    /**
     * 参与组合的，元素和下标关系
     */
    private Map<String, Integer> elementIndexMap = new HashMap<>();

    /**
     * 冲突的元素
     */
    private Map<String, Set<String>> conflictElement = new HashMap<>();

    /**
     * 冲突的元素下标
     */
    private Map<Integer, List<Integer>> conflictElementIndex = new HashMap<>();

    /**
     * 参与组合的长度数，会拿下标组合
     */
    private int elementNum;

    /**
     * 最大组合数
     */
    private int maxGroup;

    private CouponCombSolution(int maxGroup, List<String> element, Map<String, Set<String>> conflictInfoMap) {
        this.maxGroup = maxGroup;
        this.element = element;
        this.elementNum = element.size();

        // 设置元素和下标关系
        for (int i = 0; i < this.elementNum; i++) {
            elementIndexMap.put(this.element.get(i), i);
        }

        // 冲突的元素设置
        if (conflictInfoMap != null && !conflictInfoMap.isEmpty()) {
            this.conflictElement = conflictInfoMap;
            this.conflictElement.forEach((elementOne, conflictElements) -> {
                // 当前元素下标
                List<Integer> conflictElementsIndex = new ArrayList<>();
                for (String conflictElement : conflictElements) {
                    conflictElementsIndex.add(elementIndexMap.get(conflictElement));
                }
                this.conflictElementIndex.put(elementIndexMap.get(elementOne), conflictElementsIndex);
            });
        }
    }

    public static CouponCombSolution build(List<String> element, int maxGroup, Map<String, Set<String>> conflictInfoMap) {
        return new CouponCombSolution(maxGroup, element, conflictInfoMap);
    }

    /**
     * 计算下标组合
     *
     * @return
     */
    public List<List<Integer>> calcToIndex() {
        List<List<Integer>> finalResult = new ArrayList<>(32);
        // 串行计算
        for (int i = 1; i <= this.maxGroup; i++) {
            this.combine(this.elementNum, i, finalResult);
        }
        return finalResult;
    }

    /**
     * 计算真实元素组合
     *
     * @return
     */
    public List<String> calcToElementToString() {
        List<List<Integer>> calcToIndexList = this.calcToIndex();
        List<String> calcToElementList = calcToIndexList.stream().map(index -> index.stream().map(element::get).collect(Collectors.joining(","))
        ).collect(Collectors.toList());
        return calcToElementList;
    }

    /**
     * 计算真实元素组合
     *
     * @return
     */
    public List<List<String>> calcToElement() {
        List<List<Integer>> calcToIndexList = this.calcToIndex();
        List<List<String>> calcToElementList = calcToIndexList.stream().map(index -> index.stream().map(element::get).collect(Collectors.toList())
        ).collect(Collectors.toList());
        return calcToElementList;
    }

    /**
     * 组合计算
     *
     * @param size     总长度
     * @param groupNum 组合数
     * @param res      结果存放
     * @return
     */
    private List<List<Integer>> combine(int size, int groupNum, List<List<Integer>> res) {
        if (size <= 0 || groupNum <= 0 || size < groupNum) {
            return res;
        }
        generateCombinations(size, groupNum, 0, new ArrayList(groupNum), res);
        return res;
    }

    /**
     * 递归方法
     *
     * @param size
     * @param groupNum
     * @param start
     * @param list
     * @param res
     */
    private void generateCombinations(int size, int groupNum, int start, List<Integer> list, List<List<Integer>> res) {
        // 组合数达到
        if (list.size() == groupNum) {
            res.add(new ArrayList(list));
            return;
        }
        // 超出
        if (start >= size) {
            return;
        }

        int len = groupNum - (list.size());
        //list当中最终应该有k个元素，当前元素为list.size() + 1，那么我们要为下次回溯留下足够多的数
        for (int i = start; i <= size - len; i++) {
            // 判断是否冲突
            if(isConflict(list, i)){
                continue;
            }

            list.add(i);
            generateCombinations(size, groupNum, i + 1, list, res);
            list.remove(list.size() - 1);

        }
    }

    /**
     * 判断当前要插入的元素下标是否冲突
     *
     * @param list
     * @param i
     * @return
     */
    private boolean isConflict(List<Integer> list, int i) {
        if(list.size() > 0 && !conflictElementIndex.isEmpty()){
            // 获取要组合数字的冲突数组
            List<Integer> conflictElementIndexInfo = conflictElementIndex.get(i);
            if(conflictElementIndexInfo!=null && !conflictElementIndexInfo.isEmpty()){
                // 如果当前组合有包含冲突组合
                return CollectionUtil.containsAny(list,conflictElementIndexInfo);
            }
        }
        return false;
    }
}