C＃ - 通过成对和匹配

因此，我卡在一个程序，我有一系列的对可能或不能够连接在一起，形成一个完整的路径通过对。我需要能够检查一对中的第二个项目是否可以匹配另一个对中的第一个项目，依此类推，直到没有剩下的对。例如，我对可能是：C＃ - 通过成对和匹配

（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]; 
}

来源

2013-04-05 noclist

首先，您需要去掉圆括号 - 如果它们出现在您的输入文件中。为此，请参阅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-05 02:45:17 Igor

太好了，谢谢！看起来我可以使用它来让我的程序工作。有一件事 - 我所有的“第二”值都附加了“\ r”（由于这些对在我的输入文件的各行上），因此永远不会等于“第一”中的值，即使数字相同。在比较之前是否有办法将这些返回字符修剪掉？再次感谢。 – noclist 2013-04-06 22:30:45

另外，当我找到第一场比赛时，我想休息吗？我需要在整个系列赛中找到一条路径，而不是在一场比赛之后才是真实的。 – noclist 2013-04-06 22:42:42

@noclist - 查看'string'的'Trim'方法。 – Igor 2013-04-08 11:28:37

警告：这没有测试！

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-05 02:45:30

您描述的问题可以转换为另一种形式;一个graph。

下面是您给出的示例的外观。

A directed graph representing your example

我画的箭头从1到5，因为有一对（1,5），等等

在这样的曲线图的路径只能去的箭头的方向。

你想知道的是：“在这张图中是否有一条路径使用每对，即遍历每条边？

这样的路径被称为Eulerian Directed Path

维基百科列出两种算法寻找这样的路径，弗勒的和Hierholzer的，这两者在1800年代后期被发现。希望这可以让你了解从哪里开始解决这个问题。

来源

2013-04-05 09:35:41 Xantix

非常有趣。这让我更多地阅读了图论和欧拉解决的“柯尼斯堡七桥”。我永远不会想到像这样的问题可以重新想象为一个图表，感谢张贴！ – noclist 2013-04-06 22:34:05

C＃ - 通过成对和匹配

回答

相关问题