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

2021-04-05 462点热度 1人点赞 0条评论

前言

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

 

 

 

admin

这个人很懒,什么都没留下

文章评论

*

code