Особый алгоритм перебора всех подмножеств мультимножества

[arseniiv]

B@R5uk в сообщении #1289196 писал(а):

Вот так?

Ага.

[B@R5uk]

Мой алгоритм прошёл боевое крещение весьма удачно. Но в более серьёзном бою потерпел поражение с превышением лимита времени. Я там, правда, на скорую руку набыдлокодил рекурсию с постоянным выделением памяти и копированием в циклах при каждом новом вызове, однако, расходы памяти не большие: 6,5 Мб для джавы это ерунда, вряд ли даже сборщик мусора вызывался. Тем не менее, почему-то долго работало очень.

Задача там такая. Дано первое множество чисел и второе множество. Первое надо разбить на подмножества так, чтобы суммы этих разбиений были в точности элементами второго множества. Гарантируется, что решение есть.

Решал я рекурсивно. Рекурсивная функция вызывается с такими аргументами: набор значений разбиваемого множества, набор маркеров для этих значений (показывающих, какие из них под какие подмножества уже заняты), набор целевых сумм подмножеств и глубина. Функция находит все неиспользованные элементы, берёт следующую целевую сумму и с помощью моего нового решателя ищет решение. Если решения нет, то возвращается неудачный результат. В противном случае есть выбор. Если функция на дне рекурсии, то результат возвращается с пометкой "удачно". Если же нет, то новые использованные элементы помечаются и производится рекурсивный вызов. Если результат этого вызова удачный, то найденное решение возвращается, а в противном случае ищется новое решение на текущей глубине.

Возможно, в этой новой более общей задаче разбиения на заданные суммы, нужно не просто использовать возможность решать более простую задачу поиска одной суммы, а придумать более глобальную оптимизацию перебора. Пока идей у меня нет.

[arseniiv]

Там ведь ещё есть ограничение — если элемент входит в блок разбиения для одной суммы, он не входит в остальные. Здесь можно опять обобщить числа вхождений 0 и 1 до $0..M$, где $M$ — число блоков разбиения, и характеристика элемента $i$ означает, что он входит в блок $i\ne0$ или что он никуда не входит, если $i = 0$. Может статься, что ноль даже не нужен, но пока не думал.

[B@R5uk]

arseniiv в сообщении #1289236 писал(а):

Здесь можно опять обобщить числа вхождений...

Тогда совершенно не понятно в каком порядке осуществлять перебор вариантов.

У меня тут есть только такая идея: упорядочить все суммы по возрастанию количества вариантов, которыми можно каждую из этих сумм получить из элементов исходного множества. Тогда полный перебор в лоб будет чутка проще, как мне кажется: в самом корне будет самая сложная сумма с наименьшим числом вариантов, а в самом конце — сумма, для которой вероятность найти решение быстро велика. Правда, не факт, что процесс упорядочивания окупиться. Подсчёт числа вариантов — вещь очень трудоёмкая.

-- 01.02.2018, 22:36 --

Провёл тут эксперимент:
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 11, 12, 12, 13, 13, 13, 14, 14, 15, 20, 21, 21, 21]


Set size: 100
Subsets found: 143378038

Считалось пару минут. Так что идея выше — плохая, там ограничение не более секунды.

[arseniiv]

B@R5uk в сообщении #1289249 писал(а):

Тогда совершенно не понятно в каком порядке осуществлять перебор вариантов.

Для первого элемента точно в любом, а вот для остальных могут появиться предпочтения, но с начала можно сделать всем один и тот же — от 1 до $M$ (если с нулём, ноль в конце по нашей сложившейся традиции).

-- Пт фев 02, 2018 03:34:40 --

Просто с одним множеством мы держим одну сумму-остаток, а с $M$ классами понадобится иметь и проверять все $M$ сумм.

[B@R5uk]

Решил попробовать теперь сделать алгоритм, работающий по системе с переменным основанием, а не двоичным. Пока сделал только упорядоченное перечисление комбинаций:

(ПРИМЕР РАЗ)

[1, 1, 0, 1, 2]
[-1, 0, 1, 1, 3]

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 2]
[0, 0, 0, 1, 2]
[0, 1, 0, 1, 2]
[1, 1, 0, 1, 2]
[1, 0, 0, 1, 2]
[0, 1, 0, 0, 2]
[1, 1, 0, 0, 2]
[1, 0, 0, 0, 2]
[0, 0, 0, 1, 1]
[0, 1, 0, 1, 1]
[1, 1, 0, 1, 1]
[1, 0, 0, 1, 1]
[0, 1, 0, 0, 1]
[1, 1, 0, 0, 1]
[1, 0, 0, 0, 1]
[0, 0, 0, 1, 0]
[0, 1, 0, 1, 0]
[1, 1, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 0, 0, 0]
[1, 1, 0, 0, 0]
[1, 0, 0, 0, 0]

(ПРИМЕР ДВА)

[2, 1, 1, 2, 0]
[-1, 0, 1, 2, 3]

[0, 0, 0, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 2, 0]
[0, 0, 1, 2, 0]
[0, 1, 1, 2, 0]
[1, 1, 1, 2, 0]
[2, 1, 1, 2, 0]
[1, 0, 1, 2, 0]
[2, 0, 1, 2, 0]
[0, 1, 0, 2, 0]
[1, 1, 0, 2, 0]
[2, 1, 0, 2, 0]
[1, 0, 0, 2, 0]
[2, 0, 0, 2, 0]
[0, 0, 1, 1, 0]
[0, 1, 1, 1, 0]
[1, 1, 1, 1, 0]
[2, 1, 1, 1, 0]
[1, 0, 1, 1, 0]
[2, 0, 1, 1, 0]
[0, 1, 0, 1, 0]
[1, 1, 0, 1, 0]
[2, 1, 0, 1, 0]
[1, 0, 0, 1, 0]
[2, 0, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 1, 1, 0, 0]
[1, 1, 1, 0, 0]
[2, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[2, 0, 1, 0, 0]
[0, 1, 0, 0, 0]
[1, 1, 0, 0, 0]
[2, 1, 0, 0, 0]
[1, 0, 0, 0, 0]
[2, 0, 0, 0, 0]

(ПРИМЕР ТРИ)

[2, 2, 2, 2, 1]
[-1, 0, 1, 2, 3]

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 1]
[0, 0, 0, 2, 1]
[0, 0, 1, 2, 1]
[0, 0, 2, 2, 1]
[0, 1, 2, 2, 1]
[0, 2, 2, 2, 1]
[1, 2, 2, 2, 1]
[2, 2, 2, 2, 1]
[1, 1, 2, 2, 1]
[2, 1, 2, 2, 1]
[1, 0, 2, 2, 1]
[2, 0, 2, 2, 1]
[0, 1, 1, 2, 1]
[0, 2, 1, 2, 1]
[1, 2, 1, 2, 1]
[2, 2, 1, 2, 1]
[1, 1, 1, 2, 1]
[2, 1, 1, 2, 1]
[1, 0, 1, 2, 1]
[2, 0, 1, 2, 1]
[0, 1, 0, 2, 1]
[0, 2, 0, 2, 1]
[1, 2, 0, 2, 1]
[2, 2, 0, 2, 1]
[1, 1, 0, 2, 1]
[2, 1, 0, 2, 1]
[1, 0, 0, 2, 1]
[2, 0, 0, 2, 1]
[0, 0, 1, 1, 1]
[0, 0, 2, 1, 1]
[0, 1, 2, 1, 1]
[0, 2, 2, 1, 1]
[1, 2, 2, 1, 1]
[2, 2, 2, 1, 1]
[1, 1, 2, 1, 1]
[2, 1, 2, 1, 1]
[1, 0, 2, 1, 1]
[2, 0, 2, 1, 1]
[0, 1, 1, 1, 1]
[0, 2, 1, 1, 1]
[1, 2, 1, 1, 1]
[2, 2, 1, 1, 1]
[1, 1, 1, 1, 1]
[2, 1, 1, 1, 1]
[1, 0, 1, 1, 1]
[2, 0, 1, 1, 1]
[0, 1, 0, 1, 1]
[0, 2, 0, 1, 1]
[1, 2, 0, 1, 1]
[2, 2, 0, 1, 1]
[1, 1, 0, 1, 1]
[2, 1, 0, 1, 1]
[1, 0, 0, 1, 1]
[2, 0, 0, 1, 1]
[0, 0, 1, 0, 1]
[0, 0, 2, 0, 1]
[0, 1, 2, 0, 1]
[0, 2, 2, 0, 1]
[1, 2, 2, 0, 1]
[2, 2, 2, 0, 1]
[1, 1, 2, 0, 1]
[2, 1, 2, 0, 1]
[1, 0, 2, 0, 1]
[2, 0, 2, 0, 1]
[0, 1, 1, 0, 1]
[0, 2, 1, 0, 1]
[1, 2, 1, 0, 1]
[2, 2, 1, 0, 1]
[1, 1, 1, 0, 1]
[2, 1, 1, 0, 1]
[1, 0, 1, 0, 1]
[2, 0, 1, 0, 1]
[0, 1, 0, 0, 1]
[0, 2, 0, 0, 1]
[1, 2, 0, 0, 1]
[2, 2, 0, 0, 1]
[1, 1, 0, 0, 1]
[2, 1, 0, 0, 1]
[1, 0, 0, 0, 1]
[2, 0, 0, 0, 1]
[0, 0, 0, 1, 0]
[0, 0, 0, 2, 0]
[0, 0, 1, 2, 0]
[0, 0, 2, 2, 0]
[0, 1, 2, 2, 0]
[0, 2, 2, 2, 0]
[1, 2, 2, 2, 0]
[2, 2, 2, 2, 0]
[1, 1, 2, 2, 0]
[2, 1, 2, 2, 0]
[1, 0, 2, 2, 0]
[2, 0, 2, 2, 0]
[0, 1, 1, 2, 0]
[0, 2, 1, 2, 0]
[1, 2, 1, 2, 0]
[2, 2, 1, 2, 0]
[1, 1, 1, 2, 0]
[2, 1, 1, 2, 0]
[1, 0, 1, 2, 0]
[2, 0, 1, 2, 0]
[0, 1, 0, 2, 0]
[0, 2, 0, 2, 0]
[1, 2, 0, 2, 0]
[2, 2, 0, 2, 0]
[1, 1, 0, 2, 0]
[2, 1, 0, 2, 0]
[1, 0, 0, 2, 0]
[2, 0, 0, 2, 0]
[0, 0, 1, 1, 0]
[0, 0, 2, 1, 0]
[0, 1, 2, 1, 0]
[0, 2, 2, 1, 0]
[1, 2, 2, 1, 0]
[2, 2, 2, 1, 0]
[1, 1, 2, 1, 0]
[2, 1, 2, 1, 0]
[1, 0, 2, 1, 0]
[2, 0, 2, 1, 0]
[0, 1, 1, 1, 0]
[0, 2, 1, 1, 0]
[1, 2, 1, 1, 0]
[2, 2, 1, 1, 0]
[1, 1, 1, 1, 0]
[2, 1, 1, 1, 0]
[1, 0, 1, 1, 0]
[2, 0, 1, 1, 0]
[0, 1, 0, 1, 0]
[0, 2, 0, 1, 0]
[1, 2, 0, 1, 0]
[2, 2, 0, 1, 0]
[1, 1, 0, 1, 0]
[2, 1, 0, 1, 0]
[1, 0, 0, 1, 0]
[2, 0, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 0, 2, 0, 0]
[0, 1, 2, 0, 0]
[0, 2, 2, 0, 0]
[1, 2, 2, 0, 0]
[2, 2, 2, 0, 0]
[1, 1, 2, 0, 0]
[2, 1, 2, 0, 0]
[1, 0, 2, 0, 0]
[2, 0, 2, 0, 0]
[0, 1, 1, 0, 0]
[0, 2, 1, 0, 0]
[1, 2, 1, 0, 0]
[2, 2, 1, 0, 0]
[1, 1, 1, 0, 0]
[2, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[2, 0, 1, 0, 0]
[0, 1, 0, 0, 0]
[0, 2, 0, 0, 0]
[1, 2, 0, 0, 0]
[2, 2, 0, 0, 0]
[1, 1, 0, 0, 0]
[2, 1, 0, 0, 0]
[1, 0, 0, 0, 0]
[2, 0, 0, 0, 0]

Код кого-нибудь интересует? Из особенностей стоит отметить, что я осуществил возможность иметь элементы с нулевым числом повторов.

arseniiv, я правильно понимаю, что теперь мой алгоритм будет в точности повторять ваш?

[B@R5uk]

Что-то пропуски в этой новой системе кажутся ещё сложнее, чем в двоичной с учётом повторов. Сразу пытаюсь сделать конечный автомат. Число состояний нового алгоритма с ходу видно, что больше числа в старом. Сейчас размышляю над движением влево, то есть над наращиванием суммы. В начале итерации возможно следующее:

1) лимит вхождений текущего элемента в текущей сумме ещё не достигнут и эта сумма меньше целевой
2) лимит вхождений элемента достигнут, но сумма меньше целевой
3) сумма больше целевой

Действия в этих ситуациях такие:
1) добавить текущий элемент в сумму
2) сдвинуться влево и добавить новый элемент в сумму (при этом сохранить для текущего элемента ссылку на правый, а для левого ссылкой станет текущий)
3) удалить одно вхождение текущего элемента из суммы, сдвинуться влево и добавить новый элемент в сумму (при этом сохранить ссылку для текущего элемента на правый, только если число вхождений текущего элемента после вычитания ненулевое, в противном случае сохранение не требуется, а ссылка на правый элемент остаётся той же)
После каждого добавления производится проверка достижения лимита вхождения и достижения/превышения целевой суммы. Более того, на этапе сдвига, если вышли за левую границу надо переключиться в другой режим — вычитание элементов и проверку недолёта.

Ссылки на элементы как всегда нужны, чтобы не искать каждый раз при откате следующий направо ненулевой элемент, а сразу достать его адрес из массива.

В общем что-то как-то много условий и ветвлений.

[arseniiv]

B@R5uk в сообщении #1289380 писал(а):

arseniiv, я правильно понимаю, что теперь мой алгоритм будет в точности повторять ваш?

Честно говоря, я не очень слежу. Но вот в примерах у вас числа вхождений то увеличиваются, то уменьшаются, а у меня только уменьшаются.

-- Пт фев 02, 2018 22:13:47 --

Или вы про новую задачу, но про неё я особо не размышлял.

-- Пт фев 02, 2018 22:22:13 --

(Оффтоп)

B@R5uk в сообщении #1289510 писал(а):

В общем что-то как-то много условий и ветвлений.

Может, не нужно алгоритм весь засовывать в пару процедур? Это и в реальности не всегда предпочтительно, и в олимпиадных алгоритмах тоже.

[B@R5uk]

arseniiv в сообщении #1289531 писал(а):

Или вы про новую задачу

Не, про старую. Хочу переработать алгоритм так, чтобы, во-первых, повторы учитывались, а во-вторых, чтобы алгоритм мог работать с нулевым числом вхождения элементов. Тогда в олимпиадной задаче для каждого вызова алгоритма не нужно будет создавать массив новой длины, можно воспользоваться статическим набором массивов, каждый раз вычитая числа вхождения для уже найденных сумм из общего числа вхождений исходного множества чисел.

arseniiv в сообщении #1289531 писал(а):

у вас числа вхождений то увеличиваются, то уменьшаются, а у меня только уменьшаются.

Как так? Ведь, например, сначала надо попробовать первое число 3 раза, а второе 1 раз, потом наоборот, первое 1 раз, а второе 3. Потом добавляется третье число и всё по новой в различных комбинациях. Разумеется, должно то уменьшаться, то увеличиваться.

[arseniiv]

Ну, я имел в виду, что для фиксированных значений набора чисел вхождений бо́льших чисел число вхождений меньшего всегда уменьшается — в частности, число вхождений самого большого всегда уменьшается, а у вас оно (оно ведь справа?) то увеличивается, то уменьшается. У меня нет.

[B@R5uk]

А можете ещё раз свой порядок перебора по-подробней объяснить?

[arseniiv]

Могу. Будем уже наконец звать последовательность весов элементов в подмножестве его характеристическим кортежем (это ведь характеристическая функция, аргументы которой упорядочили); вес может быть неизвестным $*$. Будем считать, что элементы идут от больших к меньшим слева направо; и будем звать элемент, число вхождений которого помечено самой левой звёздочкой, предтекущим, и того, который перед ним, текущим (когда эти понятия не определены, они в алгоритме не используются).

Инициализация:
Характеристический кортеж имеет вид $(*,\ldots,*)$ (так что предтекущий элемент — первый, самый большой) и статус ?.

Шаг:
Смотрим статус.*

• Если статус — ?, узнаём (см. ниже), какое наибольшее число $n$ вхождений предтекущего элемента нам позволено сейчас иметь, и заменяем самую левую звёздочку им. Сообщаем оценивающей части, что прибавилось $n$ этого (теперь уже текущего) элемента. Ставим статус, который дадут (см. ниже).

• Если статус — =, уменьшаем число вхождений текущего элемента на 1. Ставим статусом ответ на сообщение об этом.

• Если статус — <, самое сложное из всего. Ставим число вхождений текущего элемента нулём (оповещаем об этом оценивающую часть, чтобы не сбилась, но статус не берём, т. к. он ещё изменится). Заменяем звёздочками все нули, подряд идущие прямо перед звёздочками. Если осталась хоть одно незвёздочное число вхождений, уменьшаем его на 1 и информируем оценщик, ставя статус тем, что придёт в ответ. Если одни звёздочки, сообщаем о конце перебора.

Вычисления оценивающей части. Хранится остаток набираемой суммы $S$, в начале равный интересующей сумме.

• Когда спрашивается максимальное допустимое число вхождений элемента, выдаётся $\min\{m,\lfloor S/w\rfloor\}$, где $m$ — число его вхождений в делимое мультимножество и $w$ — его вес.

• При сообщении о том, что некоторого элемента, вес которого $w$, стало на $\Delta$ больше, делается следующее: $S$ уменьшается на $w\Delta$; если теперь полная сумма элементов, скрывающихся за звёздочками (берущаяся из массива частичных сумм, конечно) меньше $S$, выходим со статусом <, в противном случае если $S = 0$, выдаём куда надо текущий характеристический кортеж, заменяя в выдаваемом $*$ нулями**, и выходим со статусом =. Если так и не вышли, выдаём статус ?.

Всё!

* Деталь реализации: у меня там ещё статус есть на случай того, что шаг вызовут уже после окончания перебора. Этот статус как раз ставится в конце, и в случае него мы сразу же выходим.
** Деталь реализации: это всегда и есть нули и ничего заменять не нужно, а начало звёздочек задаётся индексом. Но все правила я описал, сначала устроив перебор руками, и там были звёздочки.

-- Сб фев 03, 2018 01:38:50 --

Теперь у желающих есть выбор: читать описание на одном непонятном языке или на другом непонятном языке.

-- Сб фев 03, 2018 01:44:40 --

Оценивающая часть выделена в надежде использовать тот же перебор для немного других задач выделения одного подмножества. (Для последней нет.)

[B@R5uk]

Допилил я таки свой вариант алгоритма с повторами:

Используется синтаксис Java

import java.util.*;

enum State {
        REPLACE, SHIFT, ADD, REMOVE, DECREASE;
}

public class StudySubsetSearch18 {
        
        private static final Random rng = new Random();
        private static final int size = 7;
        private static final int[] entryValues = new int[size];
        private static final int[] cumulativeSums = new int[size];
        private static final int[] entryLimits = new int[size];
        private static final int[] entryCounts = new int[size];
        private static final int[] entryToTheLeft = new int[size];
        private static final int[] entryToTheRight = new int[size];
        private static int firstEntry, index, leftEntryIndex, rightEntryIndex, sum, tagetSum;
        private static State state;
        
        public static void main(String[] args) {
                int n, value, totalSum, iterationCount;
                boolean isActive;
                value = 0;
                for (n = 0; size > n; ++n) {
                        value += 1 + rng.nextInt(3);
                        entryValues[n] = value;
                }
                for (n = 0; size > n; ++n) {
                        entryLimits[n] = rng.nextInt(4);
                }
                
                System.out.println(Arrays.toString(entryValues));
                System.out.println(Arrays.toString(entryLimits));
                
                index = -1;
                firstEntry = -1;
                sum = 0;
                for (n = 0; size > n; ++n) {
                        sum += entryLimits[n] * entryValues[n];
                        cumulativeSums[n] = sum;
                        entryToTheLeft[n] = index;
                        if (0 != entryLimits[n]) {
                                index = n;
                                if (-1 == firstEntry) {
                                        firstEntry = n;
                                }
                        }
                }
                
                tagetSum = 1 + (sum >> 3) + rng.nextInt((3 * sum) >> 2);
                System.out.println(tagetSum);
                System.out.println();
                
                leftEntryIndex = entryToTheLeft[index];
                rightEntryIndex = size;
                sum = 0;
                iterationCount = 0;
                state = State.ADD;
                isActive = true;
                while (isActive) {
                        switch(state) {
                        case REPLACE:
                                sum -= entryValues[index];
                                --entryCounts[index];
                        case SHIFT:
                                if (0 != entryCounts[index]) {
                                        entryToTheRight[index] = rightEntryIndex;
                                        rightEntryIndex = index;
                                }
                                index = leftEntryIndex;
                                leftEntryIndex = entryToTheLeft[index];
                        case ADD:
                                sum += entryValues[index];
                                ++entryCounts[index];
                                display(-11, sum);
                                if (tagetSum <= sum) {
                                        if (tagetSum == sum) {
                                                System.out.print(" Match!");
                                        } else {
                                                System.out.print(" Overshort");
                                        }
                                        if (-1 == leftEntryIndex) {
                                                state = State.REMOVE;
                                        } else {
                                                state = State.REPLACE;
                                        }
                                } else {
                                        if (entryLimits[index] == entryCounts[index]) {
                                                if (-1 == leftEntryIndex) {
                                                        state = State.REMOVE;
                                                } else {
                                                        entryToTheRight[index] = rightEntryIndex;
                                                        rightEntryIndex = index;
                                                        index = leftEntryIndex;
                                                        leftEntryIndex = entryToTheLeft[index];
                                                        state = State.ADD;
                                                }
                                        } else {
                                                state = State.ADD;
                                        }
                                }
                                System.out.println();
                                break;
                        case REMOVE:
                                sum -= entryCounts[index] * entryValues[index];
                                entryCounts[index] = 0;
                        case DECREASE:
                                if (size == rightEntryIndex) {
                                        display(-1, sum);
                                        System.out.println(" End");
                                        isActive = false;
                                        break;
                                }
                                leftEntryIndex = entryToTheLeft[rightEntryIndex];
                                index = rightEntryIndex;
                                rightEntryIndex = entryToTheRight[index];
                                sum -= entryValues[index];
                                --entryCounts[index];
                                totalSum = cumulativeSums[leftEntryIndex] + sum;
                                display(leftEntryIndex, totalSum);
                                if (tagetSum >= totalSum) {
                                        if (tagetSum == totalSum) {
                                                System.out.print(" Match!");
                                        } else {
                                                System.out.print(" Undershort");
                                        }
                                        if (0 == entryCounts[index]) {
                                                state = State.DECREASE;
                                        } else {
                                                state = State.REMOVE;
                                        }
                                } else {
                                        state = State.SHIFT;
                                }
                                System.out.println();
                        }
                        ++iterationCount;
                        if (1000 == iterationCount) {
                                break;
                        }
                }
        }
        
        private static void display(int index, int sum) {
                System.out.print("[");
                for (int n = 0; size > n; ++n) {
                        if (0 != n) {
                                System.out.print(", ");
                        }
                        if (index >= n) {
                                System.out.print("x");
                        } else {
                                System.out.print(entryCounts[n]);
                        }
                }
                System.out.print("] -> ");
                System.out.print(sum);
        }
}
 

Результаты получаются такие:

(НОМЕР РАЗ)

[2, 5, 7, 8, 10, 13, 14]
[2, 1, 1, 3, 1, 3, 3]
64

[0, 0, 0, 0, 0, 0, 1] -> 14
[0, 0, 0, 0, 0, 0, 2] -> 28
[0, 0, 0, 0, 0, 0, 3] -> 42
[0, 0, 0, 0, 0, 1, 3] -> 55
[0, 0, 0, 0, 0, 2, 3] -> 68 Overshort
[0, 0, 0, 0, 1, 1, 3] -> 65 Overshort
[0, 0, 0, 1, 0, 1, 3] -> 63
[0, 0, 0, 2, 0, 1, 3] -> 71 Overshort
[0, 0, 1, 1, 0, 1, 3] -> 70 Overshort
[0, 1, 0, 1, 0, 1, 3] -> 68 Overshort
[1, 0, 0, 1, 0, 1, 3] -> 65 Overshort
[x, x, x, 0, 0, 1, 3] -> 71
[0, 0, 1, 0, 0, 1, 3] -> 62
[0, 1, 1, 0, 0, 1, 3] -> 67 Overshort
[1, 0, 1, 0, 0, 1, 3] -> 64 Match!
[x, x, 0, 0, 0, 1, 3] -> 64 Match!
[x, x, x, x, x, 0, 3] -> 92
[0, 0, 0, 0, 1, 0, 3] -> 52
[0, 0, 0, 1, 1, 0, 3] -> 60
[0, 0, 0, 2, 1, 0, 3] -> 68 Overshort
[0, 0, 1, 1, 1, 0, 3] -> 67 Overshort
[0, 1, 0, 1, 1, 0, 3] -> 65 Overshort
[1, 0, 0, 1, 1, 0, 3] -> 62
[2, 0, 0, 1, 1, 0, 3] -> 64 Match!
[x, x, x, 0, 1, 0, 3] -> 68
[0, 0, 1, 0, 1, 0, 3] -> 59
[0, 1, 1, 0, 1, 0, 3] -> 64 Match!
[1, 0, 1, 0, 1, 0, 3] -> 61
[2, 0, 1, 0, 1, 0, 3] -> 63
[x, x, 0, 0, 1, 0, 3] -> 61 Undershort
[x, x, x, x, 0, 0, 3] -> 82
[0, 0, 0, 1, 0, 0, 3] -> 50
[0, 0, 0, 2, 0, 0, 3] -> 58
[0, 0, 0, 3, 0, 0, 3] -> 66 Overshort
[0, 0, 1, 2, 0, 0, 3] -> 65 Overshort
[0, 1, 0, 2, 0, 0, 3] -> 63
[1, 1, 0, 2, 0, 0, 3] -> 65 Overshort
[x, 0, 0, 2, 0, 0, 3] -> 62 Undershort
[x, x, x, 1, 0, 0, 3] -> 66
[0, 0, 1, 1, 0, 0, 3] -> 57
[0, 1, 1, 1, 0, 0, 3] -> 62
[1, 1, 1, 1, 0, 0, 3] -> 64 Match!
[x, 0, 1, 1, 0, 0, 3] -> 61 Undershort
[x, x, 0, 1, 0, 0, 3] -> 59 Undershort
[x, x, x, 0, 0, 0, 3] -> 58 Undershort
[x, x, x, x, x, x, 2] -> 117
[0, 0, 0, 0, 0, 1, 2] -> 41
[0, 0, 0, 0, 0, 2, 2] -> 54
[0, 0, 0, 0, 0, 3, 2] -> 67 Overshort
[0, 0, 0, 0, 1, 2, 2] -> 64 Match!
[0, 0, 0, 1, 0, 2, 2] -> 62
[0, 0, 0, 2, 0, 2, 2] -> 70 Overshort
[0, 0, 1, 1, 0, 2, 2] -> 69 Overshort
[0, 1, 0, 1, 0, 2, 2] -> 67 Overshort
[1, 0, 0, 1, 0, 2, 2] -> 64 Match!
[x, x, x, 0, 0, 2, 2] -> 70
[0, 0, 1, 0, 0, 2, 2] -> 61
[0, 1, 1, 0, 0, 2, 2] -> 66 Overshort
[1, 0, 1, 0, 0, 2, 2] -> 63
[2, 0, 1, 0, 0, 2, 2] -> 65 Overshort
[x, x, 0, 0, 0, 2, 2] -> 63 Undershort
[x, x, x, x, x, 1, 2] -> 91
[0, 0, 0, 0, 1, 1, 2] -> 51
[0, 0, 0, 1, 1, 1, 2] -> 59
[0, 0, 0, 2, 1, 1, 2] -> 67 Overshort
[0, 0, 1, 1, 1, 1, 2] -> 66 Overshort
[0, 1, 0, 1, 1, 1, 2] -> 64 Match!
[1, 0, 0, 1, 1, 1, 2] -> 61
[2, 0, 0, 1, 1, 1, 2] -> 63
[x, x, x, 0, 1, 1, 2] -> 67
[0, 0, 1, 0, 1, 1, 2] -> 58
[0, 1, 1, 0, 1, 1, 2] -> 63
[1, 1, 1, 0, 1, 1, 2] -> 65 Overshort
[x, 0, 1, 0, 1, 1, 2] -> 62 Undershort
[x, x, 0, 0, 1, 1, 2] -> 60 Undershort
[x, x, x, x, 0, 1, 2] -> 81
[0, 0, 0, 1, 0, 1, 2] -> 49
[0, 0, 0, 2, 0, 1, 2] -> 57
[0, 0, 0, 3, 0, 1, 2] -> 65 Overshort
[0, 0, 1, 2, 0, 1, 2] -> 64 Match!
[0, 1, 0, 2, 0, 1, 2] -> 62
[1, 1, 0, 2, 0, 1, 2] -> 64 Match!
[x, 0, 0, 2, 0, 1, 2] -> 61 Undershort
[x, x, x, 1, 0, 1, 2] -> 65
[0, 0, 1, 1, 0, 1, 2] -> 56
[0, 1, 1, 1, 0, 1, 2] -> 61
[1, 1, 1, 1, 0, 1, 2] -> 63
[2, 1, 1, 1, 0, 1, 2] -> 65 Overshort
[x, 0, 1, 1, 0, 1, 2] -> 60 Undershort
[x, x, 0, 1, 0, 1, 2] -> 58 Undershort
[x, x, x, 0, 0, 1, 2] -> 57 Undershort
[x, x, x, x, x, 0, 2] -> 78
[0, 0, 0, 0, 1, 0, 2] -> 38
[0, 0, 0, 1, 1, 0, 2] -> 46
[0, 0, 0, 2, 1, 0, 2] -> 54
[0, 0, 0, 3, 1, 0, 2] -> 62
[0, 0, 1, 3, 1, 0, 2] -> 69 Overshort
[0, 1, 0, 3, 1, 0, 2] -> 67 Overshort
[1, 0, 0, 3, 1, 0, 2] -> 64 Match!
[x, x, x, 2, 1, 0, 2] -> 70
[0, 0, 1, 2, 1, 0, 2] -> 61
[0, 1, 1, 2, 1, 0, 2] -> 66 Overshort
[1, 0, 1, 2, 1, 0, 2] -> 63
[2, 0, 1, 2, 1, 0, 2] -> 65 Overshort
[x, x, 0, 2, 1, 0, 2] -> 63 Undershort
[x, x, x, 1, 1, 0, 2] -> 62 Undershort
[x, x, x, x, 0, 0, 2] -> 68
[0, 0, 0, 1, 0, 0, 2] -> 36
[0, 0, 0, 2, 0, 0, 2] -> 44
[0, 0, 0, 3, 0, 0, 2] -> 52
[0, 0, 1, 3, 0, 0, 2] -> 59
[0, 1, 1, 3, 0, 0, 2] -> 64 Match!
[1, 0, 1, 3, 0, 0, 2] -> 61
[2, 0, 1, 3, 0, 0, 2] -> 63
[x, x, 0, 3, 0, 0, 2] -> 61 Undershort
[x, x, x, 2, 0, 0, 2] -> 60 Undershort
[x, x, x, x, x, x, 1] -> 103
[0, 0, 0, 0, 0, 1, 1] -> 27
[0, 0, 0, 0, 0, 2, 1] -> 40
[0, 0, 0, 0, 0, 3, 1] -> 53
[0, 0, 0, 0, 1, 3, 1] -> 63
[0, 0, 0, 1, 1, 3, 1] -> 71 Overshort
[0, 0, 1, 0, 1, 3, 1] -> 70 Overshort
[0, 1, 0, 0, 1, 3, 1] -> 68 Overshort
[1, 0, 0, 0, 1, 3, 1] -> 65 Overshort
[x, x, x, x, 0, 3, 1] -> 93
[0, 0, 0, 1, 0, 3, 1] -> 61
[0, 0, 0, 2, 0, 3, 1] -> 69 Overshort
[0, 0, 1, 1, 0, 3, 1] -> 68 Overshort
[0, 1, 0, 1, 0, 3, 1] -> 66 Overshort
[1, 0, 0, 1, 0, 3, 1] -> 63
[2, 0, 0, 1, 0, 3, 1] -> 65 Overshort
[x, x, x, 0, 0, 3, 1] -> 69
[0, 0, 1, 0, 0, 3, 1] -> 60
[0, 1, 1, 0, 0, 3, 1] -> 65 Overshort
[1, 0, 1, 0, 0, 3, 1] -> 62
[2, 0, 1, 0, 0, 3, 1] -> 64 Match!
[x, x, 0, 0, 0, 3, 1] -> 62 Undershort
[x, x, x, x, x, 2, 1] -> 90
[0, 0, 0, 0, 1, 2, 1] -> 50
[0, 0, 0, 1, 1, 2, 1] -> 58
[0, 0, 0, 2, 1, 2, 1] -> 66 Overshort
[0, 0, 1, 1, 1, 2, 1] -> 65 Overshort
[0, 1, 0, 1, 1, 2, 1] -> 63
[1, 1, 0, 1, 1, 2, 1] -> 65 Overshort
[x, 0, 0, 1, 1, 2, 1] -> 62 Undershort
[x, x, x, 0, 1, 2, 1] -> 66
[0, 0, 1, 0, 1, 2, 1] -> 57
[0, 1, 1, 0, 1, 2, 1] -> 62
[1, 1, 1, 0, 1, 2, 1] -> 64 Match!
[x, 0, 1, 0, 1, 2, 1] -> 61 Undershort
[x, x, 0, 0, 1, 2, 1] -> 59 Undershort
[x, x, x, x, 0, 2, 1] -> 80
[0, 0, 0, 1, 0, 2, 1] -> 48
[0, 0, 0, 2, 0, 2, 1] -> 56
[0, 0, 0, 3, 0, 2, 1] -> 64 Match!
[0, 0, 1, 2, 0, 2, 1] -> 63
[0, 1, 1, 2, 0, 2, 1] -> 68 Overshort
[1, 0, 1, 2, 0, 2, 1] -> 65 Overshort
[x, x, 0, 2, 0, 2, 1] -> 65
[0, 1, 0, 2, 0, 2, 1] -> 61
[1, 1, 0, 2, 0, 2, 1] -> 63
[2, 1, 0, 2, 0, 2, 1] -> 65 Overshort
[x, 0, 0, 2, 0, 2, 1] -> 60 Undershort
[x, x, x, 1, 0, 2, 1] -> 64 Match!
[x, x, x, x, x, 1, 1] -> 77
[0, 0, 0, 0, 1, 1, 1] -> 37
[0, 0, 0, 1, 1, 1, 1] -> 45
[0, 0, 0, 2, 1, 1, 1] -> 53
[0, 0, 0, 3, 1, 1, 1] -> 61
[0, 0, 1, 3, 1, 1, 1] -> 68 Overshort
[0, 1, 0, 3, 1, 1, 1] -> 66 Overshort
[1, 0, 0, 3, 1, 1, 1] -> 63
[2, 0, 0, 3, 1, 1, 1] -> 65 Overshort
[x, x, x, 2, 1, 1, 1] -> 69
[0, 0, 1, 2, 1, 1, 1] -> 60
[0, 1, 1, 2, 1, 1, 1] -> 65 Overshort
[1, 0, 1, 2, 1, 1, 1] -> 62
[2, 0, 1, 2, 1, 1, 1] -> 64 Match!
[x, x, 0, 2, 1, 1, 1] -> 62 Undershort
[x, x, x, 1, 1, 1, 1] -> 61 Undershort
[x, x, x, x, 0, 1, 1] -> 67
[0, 0, 0, 1, 0, 1, 1] -> 35
[0, 0, 0, 2, 0, 1, 1] -> 43
[0, 0, 0, 3, 0, 1, 1] -> 51
[0, 0, 1, 3, 0, 1, 1] -> 58
[0, 1, 1, 3, 0, 1, 1] -> 63
[1, 1, 1, 3, 0, 1, 1] -> 65 Overshort
[x, 0, 1, 3, 0, 1, 1] -> 62 Undershort
[x, x, 0, 3, 0, 1, 1] -> 60 Undershort
[x, x, x, 2, 0, 1, 1] -> 59 Undershort
[x, x, x, x, x, 0, 1] -> 64 Match!
[x, x, x, x, x, x, 0] -> 89
[0, 0, 0, 0, 0, 1, 0] -> 13
[0, 0, 0, 0, 0, 2, 0] -> 26
[0, 0, 0, 0, 0, 3, 0] -> 39
[0, 0, 0, 0, 1, 3, 0] -> 49
[0, 0, 0, 1, 1, 3, 0] -> 57
[0, 0, 0, 2, 1, 3, 0] -> 65 Overshort
[0, 0, 1, 1, 1, 3, 0] -> 64 Match!
[0, 1, 0, 1, 1, 3, 0] -> 62
[1, 1, 0, 1, 1, 3, 0] -> 64 Match!
[x, 0, 0, 1, 1, 3, 0] -> 61 Undershort
[x, x, x, 0, 1, 3, 0] -> 65
[0, 0, 1, 0, 1, 3, 0] -> 56
[0, 1, 1, 0, 1, 3, 0] -> 61
[1, 1, 1, 0, 1, 3, 0] -> 63
[2, 1, 1, 0, 1, 3, 0] -> 65 Overshort
[x, 0, 1, 0, 1, 3, 0] -> 60 Undershort
[x, x, 0, 0, 1, 3, 0] -> 58 Undershort
[x, x, x, x, 0, 3, 0] -> 79
[0, 0, 0, 1, 0, 3, 0] -> 47
[0, 0, 0, 2, 0, 3, 0] -> 55
[0, 0, 0, 3, 0, 3, 0] -> 63
[0, 0, 1, 3, 0, 3, 0] -> 70 Overshort
[0, 1, 0, 3, 0, 3, 0] -> 68 Overshort
[1, 0, 0, 3, 0, 3, 0] -> 65 Overshort
[x, x, x, 2, 0, 3, 0] -> 71
[0, 0, 1, 2, 0, 3, 0] -> 62
[0, 1, 1, 2, 0, 3, 0] -> 67 Overshort
[1, 0, 1, 2, 0, 3, 0] -> 64 Match!
[x, x, 0, 2, 0, 3, 0] -> 64 Match!
[x, x, x, 1, 0, 3, 0] -> 63 Undershort
[x, x, x, x, x, 2, 0] -> 76
[0, 0, 0, 0, 1, 2, 0] -> 36
[0, 0, 0, 1, 1, 2, 0] -> 44
[0, 0, 0, 2, 1, 2, 0] -> 52
[0, 0, 0, 3, 1, 2, 0] -> 60
[0, 0, 1, 3, 1, 2, 0] -> 67 Overshort
[0, 1, 0, 3, 1, 2, 0] -> 65 Overshort
[1, 0, 0, 3, 1, 2, 0] -> 62
[2, 0, 0, 3, 1, 2, 0] -> 64 Match!
[x, x, x, 2, 1, 2, 0] -> 68
[0, 0, 1, 2, 1, 2, 0] -> 59
[0, 1, 1, 2, 1, 2, 0] -> 64 Match!
[1, 0, 1, 2, 1, 2, 0] -> 61
[2, 0, 1, 2, 1, 2, 0] -> 63
[x, x, 0, 2, 1, 2, 0] -> 61 Undershort
[x, x, x, 1, 1, 2, 0] -> 60 Undershort
[x, x, x, x, 0, 2, 0] -> 66
[0, 0, 0, 1, 0, 2, 0] -> 34
[0, 0, 0, 2, 0, 2, 0] -> 42
[0, 0, 0, 3, 0, 2, 0] -> 50
[0, 0, 1, 3, 0, 2, 0] -> 57
[0, 1, 1, 3, 0, 2, 0] -> 62
[1, 1, 1, 3, 0, 2, 0] -> 64 Match!
[x, 0, 1, 3, 0, 2, 0] -> 61 Undershort
[x, x, 0, 3, 0, 2, 0] -> 59 Undershort
[x, x, x, 2, 0, 2, 0] -> 58 Undershort
[x, x, x, x, x, 1, 0] -> 63 Undershort
[0, 0, 0, 0, 0, 0, 0] -> 0 End

(НОМЕР ДВА)

[3, 6, 7, 10, 12, 13, 14]
[0, 3, 2, 2, 1, 1, 0]
24

[0, 0, 0, 0, 0, 1, 0] -> 13
[0, 0, 0, 0, 1, 1, 0] -> 25 Overshort
[0, 0, 0, 1, 0, 1, 0] -> 23
[0, 0, 0, 2, 0, 1, 0] -> 33 Overshort
[0, 0, 1, 1, 0, 1, 0] -> 30 Overshort
[0, 1, 0, 1, 0, 1, 0] -> 29 Overshort
[x, x, x, 0, 0, 1, 0] -> 45
[0, 0, 1, 0, 0, 1, 0] -> 20
[0, 0, 2, 0, 0, 1, 0] -> 27 Overshort
[0, 1, 1, 0, 0, 1, 0] -> 26 Overshort
[x, x, 0, 0, 0, 1, 0] -> 31
[0, 1, 0, 0, 0, 1, 0] -> 19
[0, 2, 0, 0, 0, 1, 0] -> 25 Overshort
[x, x, x, x, x, 0, 0] -> 64
[0, 0, 0, 0, 1, 0, 0] -> 12
[0, 0, 0, 1, 1, 0, 0] -> 22
[0, 0, 0, 2, 1, 0, 0] -> 32 Overshort
[0, 0, 1, 1, 1, 0, 0] -> 29 Overshort
[0, 1, 0, 1, 1, 0, 0] -> 28 Overshort
[x, x, x, 0, 1, 0, 0] -> 44
[0, 0, 1, 0, 1, 0, 0] -> 19
[0, 0, 2, 0, 1, 0, 0] -> 26 Overshort
[0, 1, 1, 0, 1, 0, 0] -> 25 Overshort
[x, x, 0, 0, 1, 0, 0] -> 30
[0, 1, 0, 0, 1, 0, 0] -> 18
[0, 2, 0, 0, 1, 0, 0] -> 24 Match!
[x, x, x, x, 0, 0, 0] -> 52
[0, 0, 0, 1, 0, 0, 0] -> 10
[0, 0, 0, 2, 0, 0, 0] -> 20
[0, 0, 1, 2, 0, 0, 0] -> 27 Overshort
[0, 1, 0, 2, 0, 0, 0] -> 26 Overshort
[x, x, x, 1, 0, 0, 0] -> 42
[0, 0, 1, 1, 0, 0, 0] -> 17
[0, 0, 2, 1, 0, 0, 0] -> 24 Match!
[0, 1, 1, 1, 0, 0, 0] -> 23
[0, 2, 1, 1, 0, 0, 0] -> 29 Overshort
[x, x, 0, 1, 0, 0, 0] -> 28
[0, 1, 0, 1, 0, 0, 0] -> 16
[0, 2, 0, 1, 0, 0, 0] -> 22
[0, 3, 0, 1, 0, 0, 0] -> 28 Overshort
[x, x, x, 0, 0, 0, 0] -> 32
[0, 0, 1, 0, 0, 0, 0] -> 7
[0, 0, 2, 0, 0, 0, 0] -> 14
[0, 1, 2, 0, 0, 0, 0] -> 20
[0, 2, 2, 0, 0, 0, 0] -> 26 Overshort
[x, x, 1, 0, 0, 0, 0] -> 25
[0, 1, 1, 0, 0, 0, 0] -> 13
[0, 2, 1, 0, 0, 0, 0] -> 19
[0, 3, 1, 0, 0, 0, 0] -> 25 Overshort
[x, x, 0, 0, 0, 0, 0] -> 18 Undershort
[0, 0, 0, 0, 0, 0, 0] -> 0 End

(НОМЕР ТРИ)

[1, 4, 6, 8, 11, 13, 16]
[2, 0, 2, 0, 2, 0, 2]
41

[0, 0, 0, 0, 0, 0, 1] -> 16
[0, 0, 0, 0, 0, 0, 2] -> 32
[0, 0, 0, 0, 1, 0, 2] -> 43 Overshort
[0, 0, 1, 0, 0, 0, 2] -> 38
[0, 0, 2, 0, 0, 0, 2] -> 44 Overshort
[1, 0, 1, 0, 0, 0, 2] -> 39
[2, 0, 1, 0, 0, 0, 2] -> 40
[x, 0, 0, 0, 0, 0, 2] -> 34 Undershort
[x, x, x, x, x, 0, 1] -> 52
[0, 0, 0, 0, 1, 0, 1] -> 27
[0, 0, 0, 0, 2, 0, 1] -> 38
[0, 0, 1, 0, 2, 0, 1] -> 44 Overshort
[1, 0, 0, 0, 2, 0, 1] -> 39
[2, 0, 0, 0, 2, 0, 1] -> 40
[x, x, x, 0, 1, 0, 1] -> 41 Match!
[x, x, x, x, x, 0, 0] -> 36 Undershort
[0, 0, 0, 0, 0, 0, 0] -> 0 End

arseniiv в сообщении #1289574 писал(а):

Теперь у желающих есть выбор: читать описание на одном непонятном языке или на другом непонятном языке.

Ну почему же непонятном? Я ваш алгоритм теперь понял и даже, думаю, смогу реализовать. В определённом смысле он мне даже кажется более рациональным, чем все те, что я до сих пор сделал.

[grizzly]

B@R5uk в сообщении #1289729 писал(а):

Результаты получаются такие:

А насколько быстрее по сравнению со старыми? Вам ведь в конкурсе всего-то пару процентов скорости нужно добавить.

[B@R5uk]

grizzly, результаты по скорости у самого алгоритма должны быть чутка хуже, чем раньше. Хотя количество итераций будет приблизительно тоже (или даже на пару-тройку меньше). Это надо потестить. Я, вообще говоря, джаву выучил только в конце ноября прошлого года за неделю до участия в конкрусе мейла-ру CodeWars. Поэтому я не знаю ни тонкостей быстродействия языка, ни даже как создавать приложений с GUI. В последнем алгоритме, возможно, можно достичь улучшения скорости, если уменьшить число индексирований массива путём введения дополнительной временной переменной, как у меня сделано для переменной index. У неё есть после- и предшественники: leftEntryIndex и rightEntryIndex. Возможно, я перегнул палку, и одну из них можно убрать. Однако, проверку того, достигло ли число вхождений текущего элемента нуля или потолка, убрать нельзя.

Но даже, если этот алгоритм будет медленнее старого, за счёт того, что он используется нулевые числа вхождений и фиксированную длину всех массивов, в более общей задаче, можно обойтись статическими массивами (выделенными единожды) и почти без копирования данных при каждом вызове этого алгоритма. Думаю, это может дать заметное ускорение работы.

Вообще, та задача очень подлая. С одной стороны, общее число решений может быть необозримо велико, а с другой — решений может быть и единицы, в зависимости от начальных данных. Хуже того, количество промежуточных решений, то есть, когда мы взяли одну сумму и нашли решение, потом взяли другую для урезанного множества слагаемых сделали то же самое и так далее, отсечение неудачных решений может происходить на самой последней сумме. Здесь выход, на мой взгляд, только один: угадать с какой суммы начать перебор, чтобы решение попалось в на самых первых попытках.