ドミノのような複雑なオブジェクトをソートする必要があります

Question

ここに状況があります。例えば、私は、このような構造（コードが簡略化される）を有する：

class Dominoe 
{ 
    ctor Dominoe(left, right)   

    string LeftSide; 
    string RightSide; 
} 

およびIは、データを持っている、幾分のように：

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

Iは、ドミノに隙間が存在しないことを知っています、繰り返さない。 このコレクションを注文する必要があるので、すべてのRightSideは適切なLeftSideに接続されます。同様に：

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

数値 - 数値ではありません。ちょっと手掛かりが必要です。

今私は2つのステップでこの作業を行っています。 Primary - 私はエントリーポイントを探しています。 LeftSideを持っているドミノは、他のドミノの右サイドには表示されません。その後、私は0のインデックスアイテムでそれを切り替えます。第二に、私は、私のエントリードミノのRightSideと同じようにLeftSideを持っている次のドミノを探しています。

私はC＃でこれをやっていますが、これは本当に問題ではありません。

問題は - 私はそれが最良のアルゴリズムだとは思わない。どんなアイデアも素晴らしいでしょう。どうも。

EDITED！

数字について話すのが悪かったです。

トレブルカード用にドミノを変更しましょう。

だから、のようになります：あなたはあなたのソリューションが動作するあなたのカードの膨大な量を持っていない限り

TravelCard ("Dublin", "New York"), TravelCard ("Moscow", "Dublin"), TravelCard ("New York", "Habana") 

Answer 1

。そうしないと、検索定数を作成し、O(N)複雑さを保つために2つの辞書を考慮することができます。

namespace ConsoleApplication 
{ 
    public class Dominoe 
    { 
     public Dominoe(int left, int right) 
     { 
      LeftSide = left; 
      RightSide = right; 
     } 

     public int LeftSide; 
     public int RightSide; 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      var input = new List<Dominoe>() 
      { 
       new Dominoe(2, 3), 
       new Dominoe(1, 2), 
       new Dominoe(4, 5), 
       new Dominoe(3, 4) 
      }; 

      var dicLeft = new Dictionary<int, Dominoe>(); 
      var dicRigth = new Dictionary<int, Dominoe>(); 

      foreach (var item in input) 
      { 
       dicLeft.Add(item.LeftSide, item); 
       dicRigth.Add(item.RightSide, item); 
      } 

      Dominoe first = null; 

      foreach(var item in input) 
      { 
       if (!dicRigth.ContainsKey(item.LeftSide)) 
       { 
        first = item; 
        break; 
       } 
      } 

      Console.WriteLine(string.Format("{0} - {1}", first.LeftSide, first.RightSide)); 

      for(int i = 0; i < input.Count - 1; i++) 
      { 
       first = dicLeft[first.RightSide]; 
       Console.WriteLine(string.Format("{0} - {1}", first.LeftSide, first.RightSide)); 
      } 

      Console.ReadLine(); 
     } 
    } 
}