language-agnostic - algorithm - 積み上げられた靴下を効率よくペアリングするには?

algorithm / sorting / matching

昨日、私はきれいな洗濯物から靴下をペアリングしていて、それをしている方法があまり効率的ではないことを理解しました。私は素朴な検索をしていました—靴下を1つ選び、そのペアを見つけるために山を「繰り返し」ました。これは、N / 2×N / 4 = Nにわたって繰り返す必要と2平均オン/ 8靴下。

Peter Mortensen



Answer #1
List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}