C# - 쌍을 통한 루핑 및 일치

Question

그래서 쌍을 통해 전체 경로를 형성하기 위해 함께 연결될 수도 있고 연결되지 않을 수도있는 일련의 쌍이있는 프로그램에 붙어 있습니다. 쌍이있는 두 번째 항목이 다른 쌍의 첫 번째 항목과 일치하는지 확인할 수 있어야합니다. 쌍이 남아 있지 않을 때까지 계속됩니다. 예를 들어, 내 쌍 수 있습니다 :

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

I 어떻게 든 쌍을 통해 반복 할 수 있어야하고 쌍의 두 번째 숫자가 다음 쌍의 첫 번째 숫자와 일치하는지에 따라 각 경로를 통해 이동하는 완전한 경로를 얻을 수 있는지 확인해야합니다. 이 예에서 출력은

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

Answer 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; 
    } 
} 

오류 검사는 독자들에게 운동으로 남아 있습니다.

Answer 2

경고 : 이것은 테스트되지 않았습니다 !!

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 
      } 
     } 
    } 
} 
} 

Answer 3

설명하는 문제를 다른 양식으로 변환 할 수 있습니다. graph.

예를 들면 다음과 같습니다.

는 I 등

쌍 (1,5)만을 화살표의 방향으로 갈 수있다 이와 같은 그래프의 경로가 이후 1 내지 5의 화살표를 끌었다.

당신이 알고 싶은 것은 : "이 그래프에는 모든 쌍을 사용하는 경로가 있습니까? 즉 모든 가장자리를 넘나들 수 있습니까?"

이러한 경로가 Eulerian Directed Path

위키 백과로 알려진이 같은 경로를 찾기위한 두 알고리즘을 나열 플러의 및 Hierholzer의, 1800 년대 후반에 발견 된 둘. 다행히도이 방법을 통해이 문제를 해결할 수있는 방법을 알 수 있습니다.