一种快速算法而不是排列

Question

我需要找到一个快速算法来解决具有以下输入和输出的问题。

输入：

n对整数作为操作数和三个运算符(+,-,*)

输出：

如果有人可以将运算符放在所有操作数之间并且结果是 n 个不同的数字，程序会说："It's possible."。否则它会说："It's impossible."。另一方面，允许重复运算符，但不允许重复结果。通常的方法是使用排列；但这非常耗时。

一个例子：

Input:
3  5 
2  1
6  3
Output:
Possible

对于此示例，一种可能性是第一对操作数使用“-”运算符，其余操作数使用“+”运算符。

有人可以帮我解决这个问题的快速算法吗（我也必须使用 c++）？

Answer 1

您可以将其转化为最大流量问题。

让我们用 N 对（方程）的数量表示。

首先，请注意，对于每一对，我们最多有三个可能的结果（因为我们有三个运算符）。

考虑所有方程式的所有可能结果的集合，让我们将这组数字表示为A

构造一个图G，会有两个特殊节点s（source），t（sink），一个节点对应[=12的每个元素=]，最后，每个 N 输入数字对都有一个节点。

G 的边将按如下方式创建：

为这些边中的每一个分配一个等于 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；

A fast algorithm instead of permutation