Combination generator

The problem

Start with a the set of positive integers 1, 2, 3, ..., N. Call that set A. Given a number 'n' satisfying 1 <= n <= N print out a set of all unique subsets of A containing n elements.

Your output should look something like this:

  • N = 4 and n = 3:
  • Input = Set a = [1,2,3,4], int n = 3
  • Output = Set x = [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]

Breaking it down

This program was written to use Guava Set utility powerSet method which returns a set of all possible subsets of a set. For example, powerSet(ImmutableSet.of(2, 3)) returns the set {{}, {2}, {3}, {2, 3}} . To satisfy the 'n' the collection must be filtered based on the sub collection.

Create method

public static Set<Integer> generateCombinations(
        Set<Integer> from,
        int size) {

    Set<Set<Integer>> elements = Sets.powerSet(from);

    Set<Integer> possibleCombinations = elements.stream().filter(p -> p.size() == size)
            .collect(Collectors.toSet());

    return possibleCombinations;
}

Running the program

public static void main(String[] args) {

    Set<Integer> general = Sets.newHashSet(1, 2, 3, 4);

    Set<Integer> combinations = generateCombinations(general, 3);

    System.out.println(combinations);
}

Output

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

Level Up

  • Is this the most efficient way to generate combinations, if not what could be done to improve it?
  • Determine other approaches could be written to solve the problem