前言
遇到一个拆迁补偿选房问题，用户动迁一共补偿500个平方的面积，有10个房型（面积在60到140平方之间）供用户选择，需要找出5套、或者6套房型，加起来最接近500平方的选房方案。
排列组合问题
从给定的元素中取出若干个元素，列出所有可能的排序结果。
网上有找到基础的做法是如下：
/**
* 组合：从数组a中选择n个数进行组合
*/
public static void combinationSelect(int a[], int n){
System.out.println(String.format("C(%d, %d)= %d", a.length, n, combination(a.length, n)));
combinationSort(a, 0, new int[a.length], 0);
}
/**
* 通过递归的方式罗列出所有的组合结果
* @param a：初始数组
* @param a_index：初始数组起始下标
* @param result：初始组合数组
* @param r_index：初始组合数组的起始下标
*/
public static void combinationSort(int[] a, int a_index, int[] result, int r_index){
int r_len = result.length;
int r_count = r_index + 1;
if(r_count > r_len){
System.out.println(Arrays.toString(result)); // 输出组合结果
return;
}
for(int i=a_index; i<a.length+r_count-r_len; i++){
result[r_index] = a[i];
combinationSort(a, i+1, result, r_index+1);
}
}
//测试
int[] a = {1, 2, 3, 4}; // 初始数组
//取出3个组合
combinationSelect(a, 3);
Java8 Stream实现排序
到了Java8，可以使用Java8 Stream更优雅简洁的方式来实现了：
首先来看对字符数组进行组合，输出组合后的字符串
/**
* 排列组合（字符重复排列）
* 内存占用：需注意结果集大小对内存的占用（list:10位，r:8，结果集:[10 ^ 8 = 100000000]，内存占用:约7G）
* @param list 待排列组合字符集合
* @param r 排列组合生成的字符串长度
* @return 指定长度的排列组合后的字符串集合
*/
public static List<String> permutation(List<String> list, int r) {
Stream<String> stream = list.stream();
for (int n = 1; n < r; n++) {
stream = stream.flatMap(str -> list.stream().map(str::concat));
}
return stream.collect(Collectors.toList());
}
/**
* 排列组合（字符重复排列）
* @param list 待排列组合字符集合
* @param r 排列组合生成的字符串长度
* @param separator 生成组合字符串中间的分隔符
* @return 指定长度的排列组合后的字符串集合
*/
public static List<String> permutationWidthSeparator(List<String> list, int r, String separator) {
Stream<String> stream = list.stream();
for (int n = 1; n < r; n++) {
stream = stream.flatMap(str -> list.stream().map(s -> str.concat(separator + s)));
}
return stream.collect(Collectors.toList());
}
/**
* 排列组合(字符不重复排列)
* 内存占用：需注意结果集大小对内存的占用（list:10位，r:8，结果集:[10! / (10-8)! = 1814400]）
* @param list 待排列组合字符集合(忽略重复字符)
* @param r 排列组合生成长度
* @return 指定长度的排列组合后的字符串集合
*/
public static List<String> permutationNoRepeat(List<String> list, int r) {
Stream<String> stream = list.stream().distinct();
for (int n = 1; n < r; n++) {
stream = stream.flatMap(str -> list.stream()
.filter(temp -> !str.contains(temp))
.map(str::concat));
}
return stream.collect(Collectors.toList());
}
//测试
List<String> list = Arrays.asList("abc".split(""));//对[a, b, c]数组，进行排列
System.out.println(permutation(list, 2));//[aa, ab, ac, ba, bb, bc, ca, cb, cc]
System.out.println(permutationWidthSeparator(list, 2, "_"));//[a_a, a_b, a_c, b_a, b_b, b_c, c_a, c_b, c_c]
Java8 Stream组合任意List，组合结果也是数组
上面组合后的结果是用String连接起来的，我们有时候还是把任意List进行排列组合，组合后的结果也是个数组，方便后续的计算（例如上面的选房问题，我们需要把房型提炼出一个Object，排列组合后的结果，再统计成总的面积，进行计算筛选排序等等）
/**
*
* @param c 需要进行组合的List
* @param r 取出的个数
* @return 返回一个c组合后的Stream，可以有重复元素
*/
// Example: If C={1,2} and r=2
// Output: {(1,2), (2,1)}
public static <T> Stream<List<T>> permutations(List<T> c, int r) {
if (r == 1) {
return c.stream().map(Arrays::asList);
} else if (r == 2) {
return c.stream().flatMap(e1 -> c.stream() // e1: refers to an element of c
.map(e2 -> Arrays.asList(e1, e2))
);
} else {
return permutations(c, r - 1).flatMap(l -> c.stream()
.map(e -> {
List<T> out = new ArrayList<>(l);
out.add(e);
return out;
}
)
);
}
}
/**
*
* @param c 需要进行组合的List
* @param r 取出的个数
* @return 返回一个c组合后的Stream，不能有重复元素
* Example: If C={1,2} and r=2
* // Output: {(1,2), (2,1)}
*/
public static <T> Stream<List<T>> permutationsNoRepeat(List<T> c, int r) {
if (r == 1) {
return c.stream().map(Arrays::asList);
} else if (r == 2) {
return c.stream().flatMap(e1 -> c.stream() // e1: refers to an element of c
.filter(e2 -> !e1.equals(e2)) // e2: refers to an element of c
.map(e2 -> Arrays.asList(e1, e2))
);
} else {
return permutations(c, r - 1).flatMap(l -> c.stream()
.filter( e -> !l.contains(e))
.map(e -> {
List<T> out = new ArrayList<>(l);
out.add(e);
return out;
}
)
);
}
}
//测试
List<String> stringList = Arrays.asList("A", "B", "C");
//允许重复
List<List<String>> sp = permutations(stringList, 3).collect(Collectors.toList());
System.out.println(sp);//[[A, A, A], [A, A, B], [A, A, C], [A, B, A], [A, B, B], [A, B, C], [A, C, A], [A, C, B], [A, C, C], [B, A, A], [B, A, B], [B, A, C], [B, B, A], [B, B, B], [B, B, C], [B, C, A], [B, C, B], [B, C, C], [C, A, A], [C, A, B], [C, A, C], [C, B, A], [C, B, B], [C, B, C], [C, C, A], [C, C, B], [C, C, C]]
//没有重复
List<List<String>> sp2 = permutationsNoRepeat(stringList, 3).collect(Collectors.toList());
System.out.println(sp2);//[[A, A, B], [A, A, C], [A, B, C], [A, C, B], [B, A, C], [B, B, A], [B, B, C], [B, C, A], [C, A, B], [C, B, A], [C, C, A], [C, C, B]]
文章评论