1

所以我被困在一个程序上，我有一系列的对，这些对可能会也可能不会连接在一起，形成一条通过这些对的完整路径。我需要能够检查一对中的第二个项目是否可以匹配另一对中的第一个项目，依此类推，直到没有任何对。例如，我的配对可能是：

(1,5)
(2,4)
(3,2)
(5,3)
(4,3)

我需要能够以某种方式遍历这些对，并根据一对的第二个数字是否与下一对的第一个数字匹配，检查我是否可以获得一条穿过每个对的完整路径。在此示例中，输出将是：

(1,5), (5,3), (3,2), (2,4), (4,3)

形成完全匹配。如果无法形成匹配，我需要报告失败。输入基于文本文件。到目前为止，我已经能够使用 Streamreader 读取文件并根据换行符拆分对，然后遍历并根据逗号将每对拆分为其项目。我对如何进行几乎一无所知，如果有人有一些想法，我将不胜感激。

StreamReader sr = new StreamReader("inputs.txt");
string line = null;
line = sr.ReadToEnd();
var str = line.Trim().Split('\n');
int length = str.Length;
int index=1;

while (index < length)
{
    var pair = str[index].Split(',');
    var item1 = pair[0];
    var item2 = pair[1];
}
4

3 回答 3

2

您描述的问题可以转换为另一种形式；图。_

这是您提供的示例的外观。

代表您的示例的有向图

我画了一个从 1 到 5 的箭头，因为有一对 (1,5) 等等。

像这样的图上的路径只能按照箭头的方向。

您想知道的是：“此图中是否有一条使用每一对的路径，即越过每条边？”

这样的路径称为欧拉有向路径

维基百科列出了两种寻找此类路径的算法，即 Fleury 和 Hierholzer，这两种算法都是在 1800 年代后期发现的。希望这能让您了解从哪里开始解决这个问题。

于 2013-04-05T09:35:41.973 回答
1

首先，您需要去掉括号 - 如果它们存在于您的输入文件中。请参阅string.Trim方法。

蛮力方法：

public class Pair
{
  public string First;
  public string Second;
}


List<Pair> pairs = new List<Pair>();
for (int index = 0; iter < str.Length; index++)
{
    var pair = str[index].Split(',');
    pairs.Add(new Pair(){First = pair[0], Second = pair[1]});
}

List<Pair> ordered = new List<Pair>();
ordered.Add(pairs[0]);
pairs.RemoveAt(0);

while (pairs.Count > 0)
{
    bool found = false;
    for (int iter = 0; iter < pairs.Count; iter++)
    {
        if (ordered[ordered.Count - 1].Second == pairs[iter].First)
        {
            ordered.Add(pairs[iter]);
            pairs.RemoveAt(iter);
            found = true;
            break;
        }
    }
    if (!found)
    {
      <report error>
      break;
    }
}

错误检查留给读者作为练习。

于 2013-04-05T02:45:17.507 回答
0

警告：这未经测试！

using System;
using System.IO;

class t1{
public static void Main(String[] args)
{
    StreamReader sr = new StreamReader("inputs.txt");
    string line = null;
    line = sr.ReadToEnd();
    var str = line.Trim().Split('\n');
    int length = str.Length;
    int[][] arr=new int[10][];//[str.Length][2];
    int index=0;

    while (index < length)
    {
        var pair = str[index].Split(',');
        var item1 = Convert.ToInt32(pair[0]);
        var item2 = Convert.ToInt32(pair[1]);
        arr[index]=new int[]{item1,item2};

        index++;
    }

    for (int i=0;i<arr.Length;i++)
    {
        for (int j=i+1;j<arr.Length;j++)
        {
            if  (arr[i][1] == arr[j][0])
            {
                    //MATCH
            }
            else
            {
                    //FAILURE
             }
        }
    }
}
}
于 2013-04-05T02:45:30.113 回答