P26 { public static <T> List<List<T>> combinations(List<T> list, int k) { if (k == 0 || list.isEmpty()) { return Collections.emptyList(); } if (k == 1) { return list.stream().map(e -> Stream.of(e).collect(toList())).collect(toList()); } Map<Boolean, List<T>> headAndTail = P17.split(list, 1); List<T> head = headAndTail.get(true); List<T> tail = headAndTail.get(false); List<List<T>> c1 = combinations(tail, (k - 1)).stream().map(e -> { List<T> l = new ArrayList<>(); l.addAll(head); l.addAll(e); return l; }).collect(Collectors.toList()); List<List<T>> c2 = combinations(tail, k); c1.addAll(c2); return c1; }  static List<List<T>> combinations(List<T> list, int k);  }
@Test public void shouldFindAllCombinationsOfSize2FromAListWithSize3() throws Exception { List<String> input = Stream.of("a", "b", "c").collect(toList()); List<List<String>> combinations = P26.combinations(input, 2); assertThat(combinations, hasSize(3)); }
@Test public void shouldFindAllCombinationsOfSize3FromAListWithSize6() throws Exception { List<String> input = Stream.of("a", "b", "c", "d", "e", "f").collect(toList()); List<List<String>> combinations = P26.combinations(input, 3); assertThat(combinations, hasSize(20)); }
@Test public void shouldFindAllCombinationsOfSize4FromAListWithSize6() throws Exception { List<String> input = Stream.of("a", "b", "c", "d", "e", "f").collect(toList()); List<List<String>> combinations = P26.combinations(input, 4); assertThat(combinations, hasSize(15)); }