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

排列组合算法

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

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
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;
}
}