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

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

前言

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

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

文章评论

  • objessody

    Pgwjde - cialis on line During the early decades of the th century the buildingblock components of DNA were identified in more detail as deoxyribose sugars phosphate groups and four types of component called nucleotide bases or simply bases. Whjmxe Fgayzs - cialis without prescription site pour achat cialis Jensxt

    2022-04-01
  • 您需要 登录 之后才可以评论