На самом деле, я думаю, вы хотите хотите лексикографический порядок, но скорее нисходящий, чем восходящий. Дополнительно:
- Из вашего описания мне не ясно, что A, B, ... D играют какую-либо роль в вашем ответе (за исключением, возможно, в качестве контейнера для значений).
- Я думаю, что ваш пример вопроса прост: «Для каждого целого числа не менее 5, вплоть до максимально возможной суммы двух значений, сколько различных пар из набора {3, 3, 2, 1} имеют суммы этого целого числа? «
- Интересной частью является досрочное спасение, когда невозможно найти возможное решение (оставшиеся достижимые суммы слишком малы).
Я опубликую пример кода позже.
Вот пример кода, который я обещал, с несколькими замечаниями:
public class Combos {
/* permanent state for instance */
private int values[];
private int length;
/* transient state during single "count" computation */
private int n;
private int limit;
private Tally<Integer> tally;
private int best[][]; // used for early-bail-out
private void initializeForCount(int n, int limit) {
this.n = n;
this.limit = limit;
best = new int[n+1][length+1];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= length - i; ++j) {
best[i][j] = values[j] + best[i-1][j+1];
}
}
}
private void countAt(int left, int start, int sum) {
if (left == 0) {
tally.inc(sum);
} else {
for (
int i = start;
i <= length - left
&& limit <= sum + best[left][i]; // bail-out-check
++i
) {
countAt(left - 1, i + 1, sum + values[i]);
}
}
}
public Tally<Integer> count(int n, int limit) {
tally = new Tally<Integer>();
if (n <= length) {
initializeForCount(n, limit);
countAt(n, 0, 0);
}
return tally;
}
public Combos(int[] values) {
this.values = values;
this.length = values.length;
}
}
Предисловие:
При этом используется небольшой вспомогательный класс Tally, который просто изолирует табуляцию (включая инициализацию для никогда ранее не замечаемых ключей). Я поставлю это в конце.
Для краткости я взял несколько ярлыков, которые не являются хорошей практикой для "настоящего" кода:
- Это не проверяет массив нулевых значений и т. Д.
- Я предполагаю, что массив значений уже отсортирован в порядке убывания, необходимом для техники раннего спасения. (Хороший производственный код будет включать сортировку.)
- Я помещаю временные данные в переменные экземпляра вместо того, чтобы передавать их в качестве аргументов среди частных методов, поддерживающих
count. Это делает этот класс не потокобезопасным.
Пояснение:
Экземпляр Combos создается с массивом целых чисел (в порядке убывания) для объединения. Массив value устанавливается один раз для каждого экземпляра, но можно сделать несколько вызовов на count с различными размерами и ограничениями населения.
Метод count запускает (в основном) стандартный рекурсивный обход уникальных комбинаций n целых чисел из values. Аргумент limit дает нижнюю границу по интересующим суммам.
Метод countAt проверяет комбинации целых чисел из values. Аргумент left - это количество целых чисел, составляющих n целых в сумме, start - позиция в values, из которой нужно искать, а sum - частичная сумма.
Механизм раннего освобождения основан на вычислении best, двумерного массива, который задает «наилучшую» сумму, достижимую из данного состояния. Значение в best[n][p] является наибольшей суммой n значений, начинающихся в позиции p оригинала values.
рекурсия countAt заканчивается, когда накапливается правильная популяция; это добавляет текущий sum (n значений) к tally. Если countAt не достиг нижнего предела, он сместит values из позиции start, чтобы увеличить текущий частичный sum, пока:
- достаточное количество позиций остается в
values для достижения указанной совокупности, а
- оставшийся
best (самый большой) промежуточный итог достаточно велик, чтобы сделать limit.
Пример прогона с данными вашего вопроса:
int[] values = {3, 3, 2, 1};
Combos mine = new Combos(values);
Tally<Integer> tally = mine.count(2, 5);
for (int i = 5; i < 9; ++i) {
int n = tally.get(i);
if (0 < n) {
System.out.println("found " + tally.get(i) + " sums of " + i);
}
}
выдаст указанные вами результаты:
found 2 sums of 5
found 1 sums of 6
Вот код Tally:
public static class Tally<T> {
private Map<T,Integer> tally = new HashMap<T,Integer>();
public Tally() {/* nothing */}
public void inc(T key) {
Integer value = tally.get(key);
if (value == null) {
value = Integer.valueOf(0);
}
tally.put(key, (value + 1));
}
public int get(T key) {
Integer result = tally.get(key);
return result == null ? 0 : result;
}
public Collection<T> keys() {
return tally.keySet();
}
}