パーミュテーションの代わりに高速アルゴリズム

Question

以下の入力と出力の問題の高速アルゴリズムを見つける必要があります。

入力：オペランドとして整数の

Nペアと3つの演算子（+、 - 、*）

出力時：

誰かがすべてのオペランドと結果の間の演算子を置くことができる場合もn個の異なる数字を入力すると、「可能です」と表示されます。さもなければ、それは言う：「それは不可能である。一方、演算子の繰り返しは許可されますが、結果は許可されません。通常の方法は、順列の使用です。それは非常に時間がかかります。

例：

Input: 
3 5 
2 1 
6 3 
Output: 
Possible 

この例の一つの可能​​性は「 - 」それらの残りのオペランドの第一の対のためのオペレータ及び「+」演算子。

は、いくつかのボディは、この問題（また、私はC++を使用する必要があります）のための高速アルゴリズムで私を助けてもいいですか？

Answer 1

これを最大フロー問題にすることができます。

は、私たちはNでペア（方程式）の数を表すとします。

最初に、各ペアについて、3つの演算子があるため、最大で3つの結果が得られることに注意してください。

は、すべての方程式から、すべての可能な結果のセットを考慮し、二つの特別なノードs（ソース）、tを有するであろうグラフG、（シンクを構築し、私たちはA

として数値のセットを示すものと）、1つのノードはAの各要素に対応し、最後には数字の入力対の1つにつき1つのノードを含む。次のようにGの

エッジが作成されます。

• エッジsからAに対応する各ノードに。
• Aからそれぞれの結果を生成することができる数値の対に対応する各ノードにAに対応する各ノードからのエッジが（各入力対が3つの異なる値を生成することができることに注意してください）。
• 各ノードからの式に対応するエッジは、シンクtになります。これらのエッジの各々すぐ1

  に等しい容量へ

割り当て、最大フローアルゴリズムを実行します。フローの値がNに等しい場合、N異なる結果を生成することができます。

実際に、シンクに到着するNのフローを持たせるには、レイヤー内のNの式のそれぞれから1のフローを持つ必要があります。Aのどの数から各方程式の単位入力フローが得られるかを調べることで解を回復することもできます。

---

はEDIT：

は、以下の入力対のために、上記のアルゴリズムのための可視化の下に見る

3 1 
2 2 
2 1 

セットAが{2, 4, 3, 0, 1}あります。いくつかの数字は複数のペアから取得できます。2 = 3 - 1 = 2 * 1。これの効果は、番号2に対応するノードが3 1のノードと2 1のノードの両方に接続されていることです。

すべての辺は単位容量（上記のとおり）を持っています。

tにsから最大フローアルゴリズムを実行した後、結果は、太字のエッジによって示され、このフローを提供する3と1つの可能な方法です。この場合に生成される溶液は、2 = 3 - 1,4 = 2 * 2,1 = 2 - 1である。