如何从一组对象中生成组合？

Question

我需要从一个包含7个对象的集合中获取所有可能的5个对象的组合。组合不允许重复（选择顺序无关，因此选择相同的对象但以不同的顺序选出来的组合被视为相同的组合）。

我已经有了实现，它运行正常并且能够产生正确的结果：

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();
}

输出结果正确：已找到21个正确的组合。

但是它使用了位运算符，在我的评估中不太可读、可维护和可扩展。我想将其重构或完全重写为更灵活和易于理解的面向对象方法。我非常想知道如何使用OOP和递归完成这个任务。

在我的项目中，我没有使用Google Guava、Apache Commons或CombinatoricsLib。而且我不想为一个方法包含整个第三方库。我在该网站上搜索类似的问题，但只找到了一个很好的清晰的排列实现：https://stackoverflow.com/a/14486955

这些情况具有类似的含义，但是对象的顺序对我来说并不重要，在我的情况下，它们被认为是相同的组合，不应计算在内。

- François Esthète

---

这并不是一个真正的面向对象编程问题；它是一个算法问题，你只需要编写一个方法即可。请参考此其他问题的示例：https://stackoverflow.com/questions/11945682/generating-ncr-combinations-of-given-set-in-java - kaya3

这个解决方案中也使用了位运算符。 - François Esthète

https://dev59.com/9nVC5IYBdhLWcg3w-mVO 中的众多算法之一可能适合您。 - Jiri Kriz

Answer 1

你可以尝试使用以下代码：

    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);
        }
    }

基本思路是只取当前位置及其之后的元素，并使用递归来混合不同的选项。

如果您想要一个更简单的方法调用，可以创建一个类似于这样的包装器方法：

    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;
    }

---

编辑： 另一种方法是创建不同的01排列（在这种情况下是5个1和2个0），以创建掩码，然后将其转换为组合。我觉得这比先前的解决方案更自然，因为它不使用循环，除了掩码应用（隐含在流操作中）：

    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);
        }
    }

包装器方法：

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;
    }

- raven1981