我需要获得所有可能的从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
这些情况的含义有些相似,但是对象的顺序对我来说并不重要,在我的情况下,它们被视为相同的组合,因此不应计算。
您可以尝试以下代码:
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;
}