Быстрый алгоритм вместо перестановки

Question

Мне нужно найти быстрый алгоритм для проблемы со следующими входами и выходами.

Вход:

п пара целых чисел в качестве операндов и три оператора (+, -, *)

Выход:

Если кто-то может поставить операторы между всеми операндами и результатами быть n разных номеров, программа скажет: «Возможно». В противном случае он скажет: «Это невозможно». С другой стороны, повторение операторов разрешено, но результаты не допускаются. Обычный метод заключается в использовании перестановки; но это занимает много времени.

Пример:

Input: 
3 5 
2 1 
6 3 
Output: 
Possible 

В этом примере одна возможность «-» оператор для первой пары операндов и оператор «+» для остальных.

Может ли какой-нибудь орган помочь мне с быстрым алгоритмом для этой проблемы (также я должен использовать C++)?

Answer 1

Вы можете превратить это в проблему с максимальным потоком.

Обозначим через N количество пар (уравнений).

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

Рассмотрим множество всех возможных результатов из всех уравнений, будем обозначать этот набор чисел, как A

Построить график G, который будет иметь два специальных узлов s (источник), t (мойку), один узел, соответствующий каждому элементу A, и, наконец, один узел для каждой из входных пар чисел N.

Края G будут созданы следующим образом:

• ребро из s к каждому узлу, соответствующий A.
• край каждого узла, соответствующий A, каждому узлу, соответствующему паре чисел, который может получить соответствующий результат от A (помните, что каждая входная пара может генерировать 3 разных значения).
• край от каждого узла, соответствующий уравнению к раковине t.

Присвоить каждый из этих ребер мощности, равных 1.

Теперь запустите алгоритм максимального потока. Если значение потока равно N, то мы можем произвести N разные результаты.

Действительно, чтобы прибыть в раковину поток N, мы должны иметь поток по одному от каждого из уравнений N в слое раньше.Мы также можем восстановить решение, посмотрев, с какого числа в A каждое уравнение получает свой единичный входной поток.

---

РЕДАКТИРОВАТЬ:

Ниже визуализации для приведенного выше алгоритма, для следующих пар входных:

3 1 
2 2 
2 1 

Множество A является {2, 4, 3, 0, 1}. Некоторые числа могут быть получены из нескольких пар, , например.2 = 3 - 1 = 2 * 1. Эффект этого заключается в том, что узел, соответствующий номеру 2, подключен к обоим узлам с 3 1, а также к одному с 2 1.

Все ребра имеют единицу мощности (как описано выше).

После запуска алгоритма максимального потока от s до t результатом является 3, и один из возможных способов доставки этого потока иллюстрируется жирным краем. Полученный в этом случае раствор составляет 2 = 3 - 1, 4 = 2 * 2, 1 = 2 - 1;