Вот два наглядных примера:
Первый пример я не правильно изобразил. Правильно будет так:
000000
000001
000011
000111
001111
011111
111111
101111
100111
100011
100001Очень похоже на то, как пропускаются недолёты, но здесь так выглядит перебор с повторяющимися элементами.
-- 30.01.2018, 00:44 --Запилил новый код для перечисления всех комбинаций с учётом повторений:
import java.util.*;
public class StudySubsetSearch13 {
private static final Random rng = new Random();
private static final int maxRand = 4;
private static final int size = 7;
private static final int[] values = new int[size];
private static final int[] entryFlags = new int[size];
private static final int[] nextEntryReference = new int[size];
private static final int[] previousGroupIndex = new int[size];
private static int index;
private static int nextEntryIndex;
private static int frontRepetitionIndex;
public static void main(String[] args) {
int n, value, lastValue, sum, tagetSum;
boolean isFlagged;
for (n = 0; size > n; n++) {
values[n] = 1 + rng.nextInt(maxRand);
}
Arrays.sort(values);
index = -1;
previousGroupIndex[0] = index;
lastValue = values[0];
sum = lastValue;
frontRepetitionIndex = 0;
isFlagged = true;
for (n = 1; size > n; n++) {
value = values[n];
sum += value;
if (lastValue != value) {
index = n - 1;
isFlagged = false;
}
if (isFlagged) {
++frontRepetitionIndex;
}
previousGroupIndex[n] = index;
lastValue = value;
}
tagetSum = sum / 3 + rng.nextInt(maxRand);
System.out.println(Arrays.toString(values));
System.out.println(Arrays.toString(previousGroupIndex));
System.out.println(tagetSum);
System.out.println();
System.out.println(frontRepetitionIndex);
System.out.println();
nextEntryIndex = size;
index = size - 1;
while (true) {
display(entryFlags);
// display(nextEntryReference);
if (-1 == index) {
index = 0;
while (true) {
entryFlags[index] = 0;
if (frontRepetitionIndex == index) {
break;
}
++index;
}
index = nextEntryReference[index];
if (size == index) {
break;
}
entryFlags[index] = 0;
nextEntryIndex = nextEntryReference[index];
index = previousGroupIndex[index];
}
entryFlags[index] = 1;
nextEntryReference[index] = nextEntryIndex;
nextEntryIndex = index;
--index;
}
}
private static void display(int[] array) {
int n, size;
size = array.length;
for (n = 0; size > n; ++n) {
System.out.print(array[n]);
}
System.out.println();
}
}
Исключительно учёт повторений, никаких пропусков по недолёту/перелёту, даже искомые суммы не считаются. Результаты примерно такие:
(ВАРИАНТ ОДИН)
[2, 2, 2, 2, 3, 3, 4]
[-1, -1, -1, -1, 3, 3, 5]
6
3
0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
0001011
0011011
0111011
1111011
0001001
0011001
0111001
1111001
0000010
0000110
0001110
0011110
0111110
1111110
0001010
0011010
0111010
1111010
0001000
0011000
0111000
1111000
(ВАРИАНТ ДВА)
[2, 3, 3, 3, 4, 4, 4]
[-1, 0, 0, 0, 3, 3, 3]
10
0
0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
1011111
1001111
1000111
0001011
0011011
0111011
1111011
1011011
1001011
1000011
0001001
0011001
0111001
1111001
1011001
1001001
1000001
0001000
0011000
0111000
1111000
1011000
1001000
1000000
(ВАРИАНТ ТРИ)
[2, 2, 3, 3, 3, 3, 4]
[-1, -1, 1, 1, 1, 1, 5]
6
1
0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
0101111
1101111
0100111
1100111
0100011
1100011
0100001
1100001
0000010
0000110
0001110
0011110
0111110
1111110
0101110
1101110
0100110
1100110
0100010
1100010
0100000
1100000
Осталось реализовать эвристические пропуски...
-- 30.01.2018, 01:01 --В конце-концов я решил использовать всё-таки двоичную систему, а не систему с переменным основанием. И не потому, что в двоичной большая часть уже работает (код приходится всё равно с нуля переписывать). В системе с переменным основанием на каждой итерации необходимо делать по крайней мере одну дополнительную проверку: при счёте вперёд — не превысил ли счётчик текущего слагаемого максимальное количество повторов этого слагаемого, а при счёте назад не равен ли он нулю. В двоичной же всё гораздо проще: записали единицу — перешли к следующему элементу, записали ноль — тоже перешли к следующему элементу. Никаких проверок, никаких лишних затрат времени. И кода меньше в разы. Как только подумаю, в каком виде хранить кумулятивные суммы для отсечения по недолёту — волосы дыбом становится. Так что мой выбор однозначен: двоичное перечисление, и ничего другого!