[Java]Java8 Stream简洁优雅实现数列排列组合(可去重复)

前言

遇到一个拆迁补偿选房问题，用户动迁一共补偿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]]