How can I iterate over all possibilites to split one ArrayList in two ArrayLists of size k and (n-k)?

Question

I am looking for a way to iterate over all possibilites to split an array list into two array lists, where the first one has k elements and the second one has the rest.

For example, in Python I would write

import itertools
my_set = {1,2,3,4,5}
k = 2
map(lambda x: (set(x), my_set-set(x)), itertools.combinations(my_set, k))

which would give:

[(set([1, 2]), set([3, 4, 5])),
 (set([1, 3]), set([2, 4, 5])), 
 (set([1, 4]), set([2, 3, 5])), 
 (set([1, 5]), set([2, 3, 4])), 
 (set([2, 3]), set([1, 4, 5])), 
 (set([2, 4]), set([1, 3, 5])), 
 (set([2, 5]), set([1, 3, 4])), 
 (set([3, 4]), set([1, 2, 5])), 
 (set([3, 5]), set([1, 2, 4])), 
 (set([4, 5]), set([1, 2, 3]))]

How can I get all k-element subsets of a given set (well, ArrayList) in Java?

Guava has [`Collections2.permutations(Collection)`](http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Collections2.html#permutations%28java.util.Collection%29), the result of that split into parts could be what you want. — zapl, Nov 26 '14 at 20:20
the doc for itertools.combinations gives an implementation in python, you probably can translate that in java — njzk2, Nov 26 '14 at 20:25
@Misch: Thanks, http://stackoverflow.com/a/16256122/562769 is similar to what I was looking for. — Martin Thoma, Nov 26 '14 at 20:44

score 1 · Answer 1 · answered Nov 26 '14 at 21:01

Using the Collections2 from Guava like mentioned from @zapl in the comments, you could do something like this in Java8:

final List<Integer> xs = Arrays.asList(1, 2, 3, 4, 5);
final int k = 2;
Collections2.permutations(xs)
    .stream()
    .map(list -> Arrays.asList(new HashSet<>(list.subList(0, k)),
        new HashSet<>(list.subList(k, xs.size()))))
    .distinct()
    .forEach(System.out::println);

Which would result in

[[1, 2], [3, 4, 5]]
[[1, 5], [2, 3, 4]]
[[1, 4], [2, 3, 5]]
[[4, 5], [1, 2, 3]]
[[1, 3], [2, 4, 5]]
[[3, 5], [1, 2, 4]]
[[3, 4], [1, 2, 5]]
[[2, 3], [1, 4, 5]]
[[2, 5], [1, 3, 4]]
[[2, 4], [1, 3, 5]]

How can I iterate over all possibilites to split one ArrayList in two ArrayLists of size k and (n-k)?

1 Answers1