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