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＃ - 通過成對和匹配

回答

相關問題