Алгоритмическая задачка

[Chiko]

Задача:

Дана последовательность чисел и целевое число. Постарайтесь создать выражения, комбинируя одно или более число из последовательностей используя сложение, вычитание, умножение, деление и скобки. Каждое число из последовательности может быть использовано только 1 раз, также все числа, включая промежуточные результаты, должны быть натуральными положительными (1,2,3... и т.д.); запрещены - отрицательные, дробные и нули.

Например:
Последовательность чисел: 1,3,7,10, 25 и 50 и целевое число 765.
Один из возможных ответов: (1+50)х(25-10).

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

Я додумался только до того что бы получить возможные комбинации сумм, результатов деления, умножения и вычитания чисел последовательности (перебором). Есть ли какой нибудь красивый алгоритм позволяющий решить эту задачу? Буду благодарен за помощь ))

Эммм, не туда, перенесите пожалуйста в Сomputer Science

P.S: Может кто знает что такое базисы Грёбнера и как с их помощью можно решить эту задачу?

[Cave]

Нельзя лучше перебора, потому что для последовательности из $n$ единиц и целевого числа $n$ есть не менее $K_n$ (число Каталана) ответов, оно имеет асимптотику не меньше $a^n$ с $a > 1$, а для решения задачи нужно вывести ответ, то есть сделать действий не меньше, чем размер ответа.
Другое дело, что возможно перебор сократить (то есть не совсем все перебирать). Если интересно, это можно обсудить.

[Chiko]

Cave, спасибо за ответ. Ясно, значит буду делать перебором. Я просто думал что моя задача схожа с этой http://algolist.ru/maths/combinat/payment1.php , и начал читать про базисы Грёбнера и иже с ними, но мне не хватает знаний в математике. Короче говоря я ничего не понял.
По поводу задачи.
Я пока дошел до того что я могу получить 5 массивов чисел с которыми можно оперировать:

1) Исходная последовательность.
2) Различные варианты сумм чисел из исходной последовательности от - перемены мест слагаемых сумма не меняется, можно оптимизировать
(я написал класс ActionResult который в конструкторе принимает 2 параметра такого же типа в которых хранятся: результат и тип (+ - * /) предыдущей операции, а так же какие числа из заданной последовательности были использованы).
3) Различные варианты перемножения чисел из исходной последовательности - та же история что с суммой.
4) Различные варианты вычитаний - оптимизации не получится, просто все варианты вычитаний.
5) Различные варианты деления.

В итоге - 5 массивов ActionResult's. Ну и тут моя фантазия иссякла, как дальше орзганизовать перебор?

[Toucan]

Chiko в сообщении #320605 писал(а):

Эммм, не туда, перенесите пожалуйста в Сomputer Science

Перенёс.

[Cave]

Про задачу с монетами. Во-первых, там требуется найти минимальное число монет, то есть один способ. Во-вторых, построение базиса Грёбнера также не является быстрой операций: в Википедии написано, что размер базиса может быть не только экспоненциальным, но и вида $a^{b^n}$, что совсем много. И, в-третьих, задачи всё же значительно отличаются - тот метод в вашем случае точно не подойдёт. Впрочем, если он вам интересен, можете его изучить по схеме группы -> кольца -> кольцо многочленов -> базисы Грёбнера.

Про вашу задачу. Какое у вас ограничение на $n$? Вообще, мне видится разумным следующий перебор: пусть $(a_i)_{i=1}^n$ - входная последовательность, тогда для всех пар $l, r$, что $1\leqslant l < r\leqslant n$, в порядке возрастания величины $r - l$ вычисляем множество всех возможных чисел, которые получаются операциями и скобками из чисел $a_l\ldots a_r$. Подсчет происходит понятным способом: пытаемся в выражение для $a_l\ldots a_r$ выделить последнюю операцию. То есть перебираем все позиции $t$, что $l\leqslant t < r$, что означает, что мы расставляем скобки как $(a_l\ldots a_t) * (a_{t+1}\dots a_r)$, вместо звёздочки пытаемся подставить все четыре операции, вместе выражений в скобкам подставляем всевозможные числа из них (они уже посчитаны и хранятся в памяти). Важно при этом каждый результат добавлять один раз, то есть поддерживать именно множество.
Чтобы уметь восстанавливать ответ, делаем стандартный трюк: для каждой пары $l, r$ и каждого числа, полученного в выражении $a_l\ldots a_r$, храним все способы получения этого числа: то есть список из троек чисел: число $t$, число, взятое слева, то есть от $(a_l\ldots a_t)$, и число, взятое справа, то есть от $(a_{t+1}\dots a_r)$.
Возможно, немного путано объяснил, но тут тот случай, когда решение гораздо проще, чем его формальное изложение. Так что я надеюсь, что вы поняли, а если нет, то задавайте вопросы.
Сложность у алгоритма высокая, памяти нужно много.