How to generate combinations from a set of objects?

Question

I need to get all possible combinations of 5 objects from set of 7 objects. Combinations without repetition (the order of selection does not matter, that's the same objects selected in different orders are regarded as the same combination).

I have implementation, it works properly and produces the correct result:

String[] vegetablesSet = {"Pepper", "Cabbage", "Tomato", "Carrot", "Beans", "Cucumber", "Peas"};
final int SALAD_COMBINATION_SIZE = 5; // Example: {"Tomato", "Cabbage", "Cucumber", "Pepper", "Carrot"} 

Set<Set<String>> allSaladCombinations = new HashSet<>();
for (int i = 1, max = 1 << vegetablesSet.length; i < max; i++) {
   Set<String> set = new HashSet<>();
   int count = 0;
   for (int j = 0, k = 1; j < vegetablesSet.length; j++, k <<= 1) {
      if ((k & i) != 0) {
         set.add(vegetablesSet[j]);
         count++;
      }
   }
   if (count == SALAD_COMBINATION_SIZE) {
      allSaladCombinations.add(set);
   }
}

for (Set<String> set : allSaladCombinations) {
   for (String vegatable : set) {
      System.out.print(vegatable + " ");
   }
   System.out.println();
}

Output is correct: 21 right combinations has been found.

But it uses a bitwise operators and in my assessment it's not very readable, maintainable and extensible. I'd like to refactor or completely rewrite it to a more flexible and understandable object oriented approach. I'm very interested in how this could be done using OOP and recursion.

I do not use in my project Google Guava, Apache Commons or CombinatoricsLib. And I'd not want to include the whole third-party library for only one method. I was searching on the site for similar issues, but have found only good clear permutation implementation: https://stackoverflow.com/a/14486955

These cases have a somewhat similar meaning, but order of objects does not matter for me, in my case they're considered the same combinations and should not be calculated.

This is not really an OOP problem; it's an algorithm problem, which you just need to write one method for. See this other question for an example: https://stackoverflow.com/questions/11945682/generating-ncr-combinations-of-given-set-in-java — kaya3, Dec 16 '19 at 06:05
One of the tons of algorithms in https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n could suit you. — Jiri Kriz, Dec 17 '19 at 16:25

raven1981 · Accepted Answer · 2019-12-19T12:05:31.383

You can give this code a try:

    public static void main(String[] args) {
        String[] vegetablesSet = { "Pepper", "Cabbage", "Tomato", "Carrot", "Beans", "Cucumber", "Peas" };
        Set<Set<String>> result = new HashSet<>();      
        combinations(vegetablesSet, new ArrayList<>(), result, 5, 0);
        result.forEach(System.out::println);
    }

    public static void combinations(String[] values, List<String> current, Set<Set<String>> accumulator, int size, int pos) {
        if (current.size() == size) {
            Set<String> toAdd = current.stream().collect(Collectors.toSet());
            if (accumulator.contains(toAdd)) {
                throw new RuntimeException("Duplicated value " + current);
            }
            accumulator.add(toAdd);
            return;
        }
        for (int i = pos; i <= values.length - size + current.size(); i++) {
            current.add(values[i]);
            combinations(values, current, accumulator, size, i + 1);
            current.remove(current.size() - 1);
        }
    }

The basic idea is taking only the elements from the current positition onwards and using the recursing to mix the different options.

If you want a simpler method call, you can create a wrapper method like this:

    public static Set<Set<String>> combinations(String[] values) {
        Set<Set<String>> result = new HashSet<>();
        combinations(values, new ArrayList<>(), result, SALAD_COMBINATION_SIZE, 0);
        return result;
    }

Edit: Another approach will be making the different permutations of ones and zeroes (5 ones and 2 zeroes in this case) to create masks that then will be converted in the combination. I feel it more natural than the previous solution, since it doesn't use loops, other than the mask application (implicit in the stream operation):

    public static void combinations2(String[] values, String current, Set<Set<String>> accumulator, int ones, int zeroes) {
        if (ones + zeroes == 0) {
            accumulator.add(IntStream.range(0, values.length)
                    .filter(position -> '1' == current.charAt(position))
                    .mapToObj(position -> values[position])
                    .collect(Collectors.toSet()));
            return;
        }
        if (ones > 0) {
            combinations2(values, current + "1", accumulator, ones - 1, zeroes);
        }
        if (zeroes > 0) {
            combinations2(values, current + "0", accumulator, ones, zeroes - 1);
        }
    }

Wrapper method:

public static Set<Set<String>> combinations(String[] values) {
        Set<Set<String>> result = new HashSet<>();
        combinations2(values, "", result, SALAD_COMBINATION_SIZE, values.length - SALAD_COMBINATION_SIZE);
        return result;
    }

How to generate combinations from a set of objects?

1 Answers1