Всем привет!
Кросспост из раздела помощь
Задача - декомпозировать введенное число на слагаемые всеми возможными способами.
Вывести каждый вариант с новой строки. Слагаемые в декомпозиции при выводе должны быть упорядочены в порядке убывания, все варианты надо вывести построчно в лексикографическом порядке, пример:
stdin
6stdout
1 1 1 1 1 1 2 1 1 1 1 2 2 1 1 2 2 2 3 1 1 1 3 2 1 3 3 4 1 1 4 2 5 1 6Допустимые аргументы в диапазоне от 1 до 40, на выполнение дается 5 секунд. Мой бенчмарк получается таким:
30: 566ms 31: 755ms 32: 1083ms 33: 1416ms 34: 1970ms 35: 2668ms 36: 3604ms 37: 4944ms 38: 6636ms 39: 8936ms 40: 12322msКод
package test;
import java.util.*;
import java.util.stream.Collectors;
public class Decompositions {
private static Map<Integer, Set<Combination>> combinations;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
combinations = new HashMap<>();
int goal = scanner.nextInt();
search(goal);
printCombinations(goal);
// for (int i = 1; i < 41; i++) {
// combinations = new HashMap<>();
// long before = new Date().getTime();
// search(i);
// long after = new Date().getTime();
// System.out.printf("%2d: %5dms%n", i, after - before);
// }
}
private static Set<Combination> search(int element) {
if (combinations.containsKey(element))
return combinations.get(element);
Set<Combination> combinationsOfElement = new HashSet<>();
combinationsOfElement.add(new Combination(Collections.singletonList(element)));
for (int i = 1; i <= element / 2; i++) {
if (element == 1)
return combinationsOfElement;
combinationsOfElement.addAll(Combination.merge(search(i), search(element - i)));
}
combinations.put(element, combinationsOfElement);
return combinationsOfElement;
}
private static void printCombinations(int goal) {
combinations.get(goal)
.stream()
.sorted(Comparator.comparing(Combination::toString))
.forEach(System.out::println);
}
private static class Combination {
private final List<Integer> elements;
public Combination(List<Integer> elements) {
elements.sort(Collections.reverseOrder());
this.elements = elements;
}
public static Set<Combination> merge(Set<Combination> a, Set<Combination> b) {
Set<Combination> merged = new HashSet<>();
for (Combination aCombination : a) {
for (Combination bCombination : b) {
List<Integer> elements = new ArrayList<>(aCombination.getElements());
elements.addAll(bCombination.getElements());
merged.add(new Combination(elements));
}
}
return merged;
}
public List<Integer> getElements() {
return elements;
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (!(o instanceof Combination))
return false;
Combination that = (Combination) o;
return this.elements.equals(that.elements);
}
@Override
public int hashCode() {
return elements.hashCode();
}
@Override
public String toString() {
return elements.stream()
.map(String::valueOf)
.collect(Collectors.joining(" "));
}
}
}
Я вижу, что у меня происходят избыточные слияния при поиске всех новых комбинаций из составляющих элементов, но не знаю, как их избежать.
Можно было бы обойтись без написания обертки, оставив просто List<Integer>, но было бы непонятнее, а на производительность не влияет, проверял.
Может я вообще излишне усложнил, кто может предложить другой вариант перебора?