algorithm - どうすれば靴下をパイルから効率的にペアリングできますか？

Question

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

コンピューター科学者として、私は自分に何ができるかを考えていました。もちろん、O（NlogN）ソリューションを実現するために、並べ替え（サイズ/色/ ...による）が思い浮かびました。

私は靴下を複製することができないので、ハッシュまたは他のインプレースではない解決策はオプションではありません（できればそれは素晴らしいかもしれませんが）。

したがって、質問は基本的に次のとおりです。

n要素を含む靴下のペアの山を考えると2n（各靴下には正確に1つの一致するペアがあると仮定します）、最大対数の余分なスペースでそれらを効率的にペアリングするための最良の方法は何ですか？（必要に応じて、その量の情報を覚えていると思います。）

次の側面に対処する回答をいただければ幸いです。

膨大な数の靴下の一般的な理論的解決策。
実際の靴下の数はそれほど多くはありません。私の配偶者は信じられません。私は30足以上持っています。（そして、私の靴下と彼女の靴下を区別するのはかなり簡単です。これも使用できますか？）
それは要素の区別の問題と同等ですか？

score 2530 · Accepted Answer

並べ替えの解決策が提案されていますが、並べ替えは少し多すぎます。順序は必要ありません。平等グループが必要です。

したがって、ハッシュで十分です（そしてより高速です）。

靴下の色ごとに、山を作ります。入力バスケット内のすべての靴下を繰り返し、それらをカラーパイルに分配します。
各パイルを反復処理し、他のメトリック（パターンなど）で2番目のパイルセットに分散します
すぐに視覚的に処理できる非常に小さな山にすべての靴下を分散させるまで、このスキームを再帰的に適用します

この種の再帰的なハッシュパーティショニングは、SQL Serverが巨大なデータセットに対してハッシュ結合またはハッシュ集計を行う必要がある場合に、実際に実行されます。ビルド入力ストリームを、独立した多くのパーティションに分散します。このスキームは、任意の量のデータと複数のCPUに線形にスケーリングします。

各バケットが非常に高速に処理されるのに十分小さいバケットを提供する配布キー（ハッシュキー）が見つかった場合は、再帰的なパーティション分割は必要ありません。残念ながら、靴下にはそのような性質はないと思います。

PairID % 10各靴下に「PairID」と呼ばれる整数がある場合、（最後の桁）に従って10個のバケットに簡単に分配できます。

私が考えることができる最高の現実世界の分割は、山の長方形を作成することです。1つの次元は色で、もう1つの次元はパターンです。なぜ長方形なのか？なぜなら、杭へのO（1）ランダムアクセスが必要だからです。（3D直方体も機能しますが、それはあまり実用的ではありません。）

アップデート：

並列処理はどうですか？複数の人間が靴下をより速く合わせることができますか？

最も単純な並列化戦略は、複数の作業者が入力バスケットから靴下を山に置くようにすることです。これは非常にスケールアップするだけです-100人が10の山を越えて戦うと想像してください。同期コスト（手の衝突や人間のコミュニケーションとして現れる）は、効率とスピードアップを破壊します（ユニバーサルスケーラビリティの法則を参照してください！）。これはデッドロックが発生しやすいですか？いいえ、各ワーカーは一度に1つのパイルにアクセスするだけでよいためです。「ロック」が1つしかない場合、デッドロックは発生しません。人間が痔核へのアクセスを調整する方法によっては、ライブロックが可能になる場合があります。彼らはただランダムなバックオフを使うかもしれませんネットワークカードのように、物理レベルでそれを実行して、どのカードがネットワークワイヤに排他的にアクセスできるかを決定します。NICで機能する場合は、人間でも機能するはずです。
各作業者が独自のパイルのセットを持っている場合、ほぼ無期限にスケーリングします。その後、作業者は入力バスケットから靴下の大きな塊を取り出すことができ（めったに行わないため、競合はほとんどありません）、靴下を配布するときに同期する必要はありません（スレッドローカルパイルがあるため）。最後に、すべての労働者はパイルセットを結合する必要があります。ワーカーが集約ツリーを形成する場合、O（ログ（ワーカー数*ワーカーあたりのパイル））で実行できると思います。

要素の区別の問題はどうですか？記事に記載されているように、要素の識別性の問題はで解決できますO(N)。これは靴下の問題についても同じです（またO(N)、1つの配布ステップのみが必要な場合（人間が計算に苦手であるという理由だけで複数のステップを提案しました-配布する場合は1つのステップで十分ですmd5(color, length, pattern, ...)。つまり、すべての属性の完全なハッシュ））。

明らかに、より速く進むことはできないので、最適な下限O(N)に達しました。

出力は完全に同じではありませんが（1つの場合はブール値、他の場合は靴下のペア）、漸近的な複雑さは同じです。

score 609 · Accepted Answer

人間の脳のアーキテクチャは現代のCPUとは完全に異なるため、この質問は実用的な意味がありません。

人間は、「一致するペアを見つける」ことが、それほど大きくないセットの1つの操作である可能性があるという事実を使用して、CPUアルゴリズムに勝つことができます。

私のアルゴリズム：

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

少なくともこれは私が実際に使用しているものであり、非常に効率的だと思います。欠点は、平らな表面が必要なことですが、通常は豊富です。

score 272 · Accepted Answer

ケース1：すべての靴下は同じです（ちなみに、これは私が実際に行っていることです）。

それらのいずれか2つを選んでペアを作ります。一定時間。

ケース2：一定数の組み合わせ（所有権、色、サイズ、テクスチャなど）があります。

基数ソートを使用します。比較が不要なため、これは線形時間のみです。

ケース3：組み合わせの数は事前にわかっていません（一般的なケース）。

2つの靴下がペアになっているかどうかを確認するために比較を行う必要があります。O(n log n)比較ベースのソートアルゴリズムの1つを選択します。

ただし、靴下の数が比較的少ない（一定の）実際の生活では、これらの理論的に最適なアルゴリズムはうまく機能しません。理論的には2次時間を必要とするシーケンシャル検索よりもさらに時間がかかる場合があります。

score 159 · Accepted Answer

非アルゴリズム的な答えですが、私がそれを行うと「効率的」です。

ステップ1）既存の靴下をすべて捨てる
ステップ2）ウォルマートに行き、10-nパケットの白とmパケットの黒でそれらを購入します。日常生活で他の色は必要ありません。

しかし、時々これをやり直さなければならず（靴下の紛失、靴下の損傷など）、完全に良い靴下を頻繁に廃棄するのは嫌いです（そして、同じ靴下のリファレンスを販売し続けたいと思っていました！）。別のアプローチ。

アルゴリズムの答え：

靴下の2番目のスタックに1つだけ靴下を引く場合よりも、素朴な検索で一致する靴下を見つける確率は非常に低いと考えてください。

それで、それらのうちの5つをランダムに拾い上げて、それらの形またはそれらの長さを覚えてください。

なぜ5つ？通常、人間は作業メモリー内の5〜7つの異なる要素を覚えているのが良いです-RPNスタックの人間の等価物に少し似ています-5は安全なデフォルトです。

2n-5のスタックから1つをピックアップします。
次に、描いた5つの中で一致するもの（視覚的なパターンマッチング-人間は小さなスタックでそれが得意です）を探します。見つからない場合は、それを5つに追加します。
スタックからランダムに靴下を選び続け、5+1の靴下と比較して一致させます。スタックが大きくなると、パフォーマンスは低下しますが、オッズは上がります。はるかに高速。

数式を書き留めて、一致の50％のオッズに対して描画する必要のあるサンプルの数を計算してください。IIRCそれは超幾何法則です。

私は毎朝それを行い、3回以上のドローが必要になることはめったにありませんが、形をした白い靴下nの同様のペア（約10、失われたものを与えるか取る）があります。m今、あなたは私の株のスタックのサイズを見積もることができます:-)

ところで、ペアが必要になるたびにすべての靴下を並べ替えるトランザクションコストの合計は、一度行って靴下をバインドするよりもはるかに少ないことがわかりました。靴下を縛る必要がないため、ジャストインタイムの方がうまく機能します。また、限界収穫逓減もあります（つまり、洗濯物のどこかにあるときに必要な2つまたは3つの靴下を探し続けます。靴下のマッチングを終えると、時間が失われます）。

score 108 · Accepted Answer

私がしていることは、最初の靴下を手に取り、それを下に置くことです（たとえば、洗濯ボウルの端に）。次に、別の靴下を手に取り、最初の靴下と同じかどうかを確認します。もしそうなら、私はそれらの両方を削除します。そうでない場合は、最初の靴下の横に置きます。次に、3つ目の靴下を手に取り、最初の2つと比較します（まだ靴下が残っている場合）。等。

~~このアプローチは、靴下の「取り外し」がオプションであると仮定すると、アレイにかなり簡単に実装できます。~~実際には、靴下を「取り除く」必要さえありません。靴下を並べ替える必要がない場合は（以下を参照）、靴下を移動するだけで、すべての靴下がペアで配列された配列になります。

靴下の唯一の操作が同等性を比較することであると仮定すると、このアルゴリズムは基本的にn ²アルゴリズムですが、平均的なケースについてはわかりません（それを計算することを学んだことはありません）。

もちろん、並べ替えは効率を向上させます。特に、他の2つの靴下の間に靴下を簡単に「挿入」できる実際の生活ではそうです。コンピューティングでは、ツリーによって同じことが達成できますが、それは余分なスペースです。そしてもちろん、NlogNに戻ってきました（並べ替え基準で同じであるが、同じペアからではない靴下がいくつかある場合は、もう少しです）。

それ以外は何も考えられませんが、実生活ではかなり効率的な方法のようです。:)

score 61 · Accepted Answer

これは間違った質問をしている。正しい質問は、なぜ靴下の仕分けに時間を費やしているのかということです。選択したX通貨単位の空き時間を評価する場合、年間ベースでいくらかかりますか？

そして、多くの場合、これは単なる自由時間ではなく、朝の自由時間であり、ベッドで過ごしたり、コーヒーを飲んだり、少し早く出発して交通渋滞に巻き込まれたりすることはありません。

一歩下がって、問題を回避する方法を考えるのは良いことです。

そして、方法があります！

あなたが好きな靴下を見つけてください。さまざまな照明条件での色、全体的な品質と耐久性、さまざまな気候条件での快適さ、臭気の吸収など、関連するすべての機能を考慮に入れてください。また重要なのは、保管時に弾力性を失わないようにすることです。そのため、天然の生地が適しています。また、プラスチックの包装で入手できる必要があります。

左右の足の靴下に違いがない方がいいですが、それは重要ではありません。靴下が左右対称の場合、ペアを見つけることはO（1）操作であり、靴下を並べ替えることはおおよそのO（M）操作です。ここで、Mは、靴下を散らかした家の場所の数です。小さな定数。

左右の靴下が異なるファンシーペアを選択した場合、左右の足のバケットに対してフルバケットソートを実行すると、O（N + M）が必要になります。ここで、Nは靴下の数で、Mは上記と同じです。他の誰かが最初のペアを見つける平均反復の式を与えることができますが、ブラインド検索でペアを見つけるための最悪のケースはN / 2 + 1であり、合理的なNの場合は天文学的にありそうもないケースになります。これは高度な画像を使用することでスピードアップできますMk1Eyeballで分類されていない靴下の山をスキャンするときの認識アルゴリズムとヒューリスティック。

したがって、O（1）ソックスペアリング効率を達成するためのアルゴリズム（対称ソックスを想定）は次のとおりです。

あなたはあなたがあなたの人生の残りのために、あるいはおそらくあなたが引退して二度と靴下を履く必要がないより暖かい気候に移るまで、あなたが必要とする靴下のペアの数を見積もる必要があります。あなたが若い場合は、私たち全員が家に靴下仕分けロボットを設置するまでにかかる時間も見積もることができ、問題全体は無関係になります。
選択した靴下をまとめて注文する方法と費用を確認し、それらを提供する必要があります。
靴下を注文してください！
古い靴下を取り除きます。

別のステップ3は、同じ量のおそらく安い靴下を何年にもわたって一度に数足購入するコストを比較し、靴下を分類するコストを追加することですが、私の言葉を借りれば、まとめて購入する方が安いです！また、ストレージの靴下は株価のインフレ率で価値が上昇します。これは、多くの投資で得られるよりも多くなります。また、保管コストもかかりますが、靴下はクローゼットの一番上の棚にあまりスペースを取りません。

問題が解決しました。だから、新しい靴下を手に入れ、古い靴下を捨てて寄付し、残りの人生のために毎日お金と時間を節約していることを知った後も幸せに暮らしましょう。

score 53 · Accepted Answer

各靴下に触れる必要があるため、理論上の制限はO（n）です（一部がすでに何らかの方法でペアリングされている場合を除く）。

基数ソートでO（n）を達成できます。バケットのいくつかの属性を選択する必要があります。

最初にあなたは（彼女、私の）を選ぶことができます-それらを2つの山に分けます、
次に、色を使用します（たとえば、色の名前のアルファベット順など、色の順序は任意です）-色ごとに山に分割します（同じ山のすべての靴下について、手順1の最初の順序を維持することを忘れないでください）。
次に靴下の長さ、
次にテクスチャ、...。

限られた数の属性を選択できるが、各ペアを一意に識別できる十分な属性がある場合は、O（k * n）で実行する必要があります。これは、kが制限されていると見なすことができる場合はO（n）です。

score 34 · Accepted Answer

実用的な解決策として：

簡単に識別できる靴下の山をすばやく作成します。（色で言う）
すべての山をクイックソートし、靴下の長さを比較に使用します。人間として、最悪の場合を回避するパーティション分割に使用するソックスをかなり迅速に決定できます。（複数の靴下を並行して見ることができます。それを活用してください！）
スポットペアとペアリングできない靴下をすぐに見つけることができるしきい値に達したら、パイルの並べ替えを停止します

1000個の靴下があり、8色で平均的な分布の場合、c*n時間で125個の靴下ごとに4つの山を作ることができます。5靴下のしきい値を使用すると、6回の実行ですべての山を並べ替えることができます。（右の山に靴下を投げるのに2秒かかると、4時間弱かかります。）

靴下が60個、3色、2種類の靴下（あなた/あなたの妻）しかない場合は、1回の実行で10個の靴下の山ごとに並べ替えることができます（しきい値= 5）。（2秒を数えると2分かかります）。

最初のバケットソートはプロセスをスピードアップします。これは、n個の靴下を時間内にk個のバケットに分割するため、作業c*nを行うだけで済みますc*n*log(k)。（しきい値を考慮していません）。つまり、全体として、あなたはn*c*(1 + log(k))仕事について行います。ここで、cは靴下を山に投げる時間です。

c*x*n + O(1)このアプローチは、おおよそ。である限り、他の方法と比較して有利log(k) < x - 1です。

コンピュータサイエンスでは、これが役立つ場合があります。n個のコレクション、それらの順序（長さ）、および同値関係（靴下の色などの追加情報）があります。同値関係により、元のコレクションのパーティションを作成でき、すべての同値類で順序が維持されます。モノの同値類へのマッピングはO（1）で実行できるため、各アイテムをクラスに割り当てるために必要なのはO（n）だけです。これで、追加情報を使用して、あらゆる方法ですべてのクラスを並べ替えることができます。利点は、データセットがすでに大幅に小さいことです。

複数の同値関係がある場合は、メソッドをネストすることもできます->テクスチャ上のすべてのパイルパーティション内よりも、長さでソートするよりも、カラーパイルを作成します。サイズがほぼ同じである2つ以上の要素でパーティションを作成する同値関係は、並べ替えよりも速度が向上し（靴下をその山に直接割り当てることができる場合）、小さなデータセットで並べ替えを非常に迅速に行うことができます。

score 32 · Accepted Answer

あなたは間違った問題を解決しようとしています。

解決策1：汚れた靴下を洗濯かごに入れるたびに、小さな結び目で結びます。そうすれば、洗濯後に仕分けをする必要がなくなります。Mongoデータベースにインデックスを登録するようなものだと考えてください。将来的にCPUを節約するために少し作業を進めてください。

解決策2：冬の場合は、おそろいの靴下を履く必要はありません。私たちはプログラマーです。それが機能する限り、誰も知る必要はありません。

解決策3：作業を広げます。UIをブロックせずに、このような複雑なCPUプロセスを非同期で実行する必要があります。その靴下の山を取り、バッグに詰めます。必要なときにだけペアを探してください。そうすれば、必要な作業量ははるかに目立たなくなります。

お役に立てれば！

score 27 · Accepted Answer

この質問は実際には非常に哲学的です。本質的には、問題を解決する人々の力（私たちの脳の「ウェットウェア」）がアルゴリズムによって達成できるものと同等であるかどうかについてです。

靴下の並べ替えの明らかなアルゴリズムは次のとおりです。

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

さて、この問題のコンピュータサイエンスはすべてステップに関するものです

「sがNの靴下tとペアになっている場合」。これまでに見たものをどれだけ早く「覚える」ことができますか？
「tをNから削除」および「sをNに追加」。これまでに見たものを追跡するのにどれくらいの費用がかかりますか？

人間はこれらを実現するためにさまざまな戦略を使用します。人間の記憶は連想的であり、格納された値の機能セットが対応する値自体とペアになっているハッシュテーブルのようなものです。たとえば、「赤い車」の概念は、人が覚えることができるすべての赤い車に対応しています。完璧な記憶を持っている人は完璧なマッピングを持っています。ほとんどの人はこの点で不完全です（そして他のほとんどの人）。連想マップの容量には制限があります。マッピングがブリーチする可能性がありますさまざまな状況で存在しなくなった（ビールが多すぎる）、誤って記録された（「彼女の名前はネティではなくベティだったが」）、または真実が変わったと観察しても上書きされない（「お父さんの車」が呼び起こす）私たちが実際に彼がそれを赤いカマロと交換したことを知ったときの「オレンジ色の火の鳥」）。

靴下の場合、完全な想起とは、靴下を見ると、s常にその兄弟の記憶が生成されることを意味します。これには、一定時間でt見つけるのに十分な情報（アイロン台にある場所）が含まれます。t写真の記憶を持っている人は、必ず1と2の両方を一定時間で達成します。

完全な記憶力に満たない人は、追跡する能力の範囲内の機能に基づいて、いくつかの常識的な同等のクラスを使用する可能性があります：サイズ（パパ、ママ、赤ちゃん）、色（緑がかった、赤みがかったなど）、パターン（アーガイル、プレーンなど）、スタイル（サッカー、ニーハイなど）。したがって、アイロン台はカテゴリごとにセクションに分割されます。これにより、通常、カテゴリをメモリによって一定時間内に配置できますが、カテゴリ「バケット」を線形検索する必要があります。

記憶や想像力がまったくない人（申し訳ありません）は、靴下を1つの山にまとめて、山全体を線形探索します。

きちんとしたフリークは、誰かが提案したように、ペアに数値ラベルを使用するかもしれません。これにより、全順序付けへの扉が開かれ、人間はCPUで使用するのとまったく同じアルゴリズム（バイナリ検索、ツリー、ハッシュなど）を使用できるようになります。

したがって、「最良の」アルゴリズムは、それを実行しているウェットウェア/ハードウェア/ソフトウェアの品質と、ペアに全順序を課すことによって「チート」する意欲に依存します。確かに、「最高の」メタアルゴリズムは、世界最高の靴下ソーターを雇うことです。一定時間のルックアップ、挿入、と削除します。このような人も機械も調達できます。靴下をお持ちの場合は、O（N）時間ですべての靴下をNペアでペアリングできます。これが最適です。全順序タグを使用すると、標準のハッシュを使用して、人間のコンピューターまたはハードウェアコンピューターのいずれかで同じ結果を得ることができます。

score 23 · Accepted Answer

これは、比較ベースのモデルにおけるOmega（n log n）の下限です。（唯一の有効な操作は、2つの靴下を比較することです。）

2n靴下が次のように配置されていることを知っているとします。

p ₁ p ₂ p ₃ ... p _n p _f（1） p _f（2） ... p _f（n）

ここで、fは集合{1,2、...、n}の未知の順列です。これを知っていても、問題を難しくすることはできません。nあります！可能な出力（前半と後半のマッチング）。これは、log（n！）= Omega（n log n）の比較が必要であることを意味します。これは、並べ替えによって取得できます。

要素の区別の問題への接続に関心があるため、出力がバイナリのyes / noであるため、要素の区別にバインドされたOmega（n log n）を証明することは困難です。ここで、出力は一致している必要があり、適切な境界を取得するには、可能な出力の数で十分です。ただし、要素の区別に関連するバリアントがあります。2nの靴下が与えられ、それらを一意にペアリングできるかどうか疑問に思ったとします。_{（a 1}、a ₂、...、a _n）を（a ₁、a ₁、a ₂、a ₂、...、a _n、a _n ）に送信することにより、EDからの削減を得ることができます。（一般的に、EDの硬度の証明はトポロジーを介して非常に興味深いものです。）

等式テストのみを許可する場合は、元の問題にOmega（n ² ）がバインドされているはずだと思います。私の直感は次のとおりです。テスト後にエッジを追加するグラフを検討し、グラフが密でない場合、出力は一意に決定されないと主張します。

score 23 · Accepted Answer

コスト：靴下の移動->高い、靴下の検索/検索->小さい

私たちがやりたいのは、移動の数を減らし、検索の数を補うことです。また、Homo Sapiensの多岐にわたる環境を利用して、より多くのものを決定キャッシュに保持することができます。

X =あなたのもの、Y=あなたの配偶者

すべての靴下の山Aから：

2つの靴下を選び、対応するX靴下をXラインに配置し、Y靴下をYラインの次の使用可能な位置に配置します。

Aが空になるまで実行します。

XとYの各行について

行の最初の靴下を選び、対応する靴下が見つかるまで行に沿って検索します。
対応する靴下の完成ラインに入れます。
オプションラインを検索しているときに、現在表示している靴下が前の靴下と同じである場合は、これらの靴下に対して手順2を実行します。

ステップ1のオプションとして、そのラインから2つではなく2つのソックスを選択します。これは、キャッシングメモリが十分に大きいため、どちらかのソックスが観察しているラインの現在のソックスと一致するかどうかをすばやく特定できるためです。幸運にも3本の腕を持っている場合は、対象の記憶が十分に大きいことを考えると、3つの靴下を同時に解析できる可能性があります。

XとYの両方が空になるまで実行します。

終わり

ただし、これは選択ソートと同様の複雑さを持っているため、I / O（靴下の移動）と検索（靴下のラインの検索）の速度により、かかる時間ははるかに短くなります。

score 22 · Accepted Answer

実際のアプローチ：

できるだけ早く、分類されていない山から靴下を1つずつ取り出し、目の前の山に置きます。パイルは、すべての靴下が同じ方向を向くように、ある程度スペース効率よく配置する必要があります。杭の数は、簡単に到達できる距離によって制限されます。靴下を置く山の選択は、明らかに靴下のような山の上に靴下を置くことによって、できるだけ早く行う必要があります。時折発生するタイプI（靴下を属していない山に置く）またはタイプII（同じような靴下の山が存在する場合に靴下を自分の山に置く）エラーは許容できます-最も重要な考慮事項は速度です。

すべての靴下が山になったら、マルチ靴下の山をすばやく通過してペアを作成し、それらを取り外します（これらは引き出しに向かっています）。一致しない靴下が山にある場合は、それらを最高の（可能な限り速い制約内で）山に再積み上げます。すべてのマルチソックスパイルが処理されたら、タイプIIエラーのためにペアリングされなかった残りのペアリング可能なソックスを一致させます。おっと、あなたは終わりました-そして私はたくさんの靴下を持っていて、大部分が汚れるまでそれらを洗わないでください。もう1つの実用的な注意：私は靴下のペアの一方の上部をもう一方の上にひっくり返し、それらの弾性特性を利用して、引き出しに運ばれている間、および引き出しの中にある間、それらが一緒にとどまるようにします。

score 21 · Accepted Answer

これは私が実際にそれを行う方法です。靴下のpペア（n = 2pの個々の靴下）の場合：

山からランダムに靴下をつかみます。
最初の靴下の場合、または以前に選択したすべての靴下がペアになっている場合は、ペアになっていない靴下の「配列」の最初の「スロット」に靴下を置くだけです。
ペアになっていない靴下を1つ以上選択している場合は、現在の靴下をアレイ内のペアになっていないすべての靴下と照合します。
- アレイを構築するときに、靴下を一般的なクラスまたはタイプ（白/黒、足首/乗組員、運動/ドレス）に分類し、「ドリルダウン」して類似点のみを比較することができます。
- 許容できる一致が見つかった場合は、両方の靴下を組み合わせて、アレイから取り外します。
- そうでない場合は、現在の靴下をアレイの最初の空きスロットに入れます。
すべての靴下で繰り返します。

このスキームの最悪のシナリオは、靴下のすべてのペアが十分に異なるため、正確に一致させる必要があり、最初に選択したn/2の靴下がすべて異なることです。これはO（n ²）シナリオであり、ほとんどありません。靴下の固有のタイプの数tがペアの数p=n / 2未満であり、各タイプの靴下が（通常は摩耗に関連する用語で）十分に類似している場合、そのタイプの靴下はその他、上記で推測したように、比較する必要のある靴下の最大数はtです。その後、次に引っ張る靴下はtになります。ペアになっていない靴下の1つと一致します。このシナリオは、平均的な靴下の引き出しで最悪の場合よりもはるかに可能性が高く、最悪の場合の複雑さをO（n * t）に減らします。ここで、通常はt<<nです。

score 16 · Accepted Answer

あなたの質問から、あなたは洗濯の実際の経験があまりないことは明らかです:)。ペアリングできない靴下の数が少ない場合にうまく機能するアルゴリズムが必要です。

これまでの答えは、人間のパターン認識機能をうまく利用していません。セットのゲームは、これをうまく行う方法の手がかりを提供します。すべての靴下を2次元空間に配置して、靴下をよく認識し、手で簡単に届くようにします。これにより、約120 *80cm程度の領域に制限されます。そこから、認識したペアを選択して削除します。空きスペースに余分な靴下を入れて繰り返します。簡単に認識できる靴下を持っている人（小さな子供が頭に浮かぶ）を洗う場合は、最初にそれらの靴下を選択することで基数ソートを行うことができます。このアルゴリズムは、シングルソックスの数が少ない場合にのみうまく機能します

score 16 · Accepted Answer

最初の靴下を手に取り、テーブルの上に置きます。次に、別の靴下を選びます。最初に選んだものと一致する場合は、最初に選んだものの上に置きます。そうでない場合は、最初のテーブルから少し離れた場所に置きます。3つ目の靴下を選びます。前の2つのいずれかに一致する場合は、それらの上に配置するか、3番目から少し離して配置します。すべての靴下を手に取るまで繰り返します。

score 13 · Accepted Answer

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

score 13 · Accepted Answer

私は、より少ない操作、より少ない時間の消費を約束しない別の解決策を思いつきましたが、それが巨大な一連の靴下のペアリングでより少ない時間の消費を提供するのに十分なヒューリスティックであるかどうかを確認する必要があります。

前提条件： 同じ靴下があるという保証はありません。それらが同じ色である場合、それはそれらが同じサイズまたはパターンを持っているという意味ではありません。靴下はランダムにシャッフルされます。靴下の数が奇数になる可能性があります（靴下の数が不足しているものもありますが、いくつあるかはわかりません）。変数「インデックス」を覚えて、0に設定する準備をします。

結果には、1つまたは2つの山があります：1。「一致」および2.「欠落」

ヒューリスティック：

最も特徴的な靴下を見つけてください。
その一致を見つけます。
一致するものがない場合は、「不足している」山に置きます。
最も特徴的な靴下がなくなるまで、1から繰り返します。
靴下が6足未満の場合は、11に進みます。
すべての靴下を隣人と盲目的にペアリングします（梱包しないでください）
一致するすべてのペアを見つけてパックし、パックされたペアを「一致する」パイルに移動します。新しい一致がなかった場合-「インデックス」を1つインクリメントします
「インデックス」が2より大きい場合（靴下の数が多いほど、盲目的にペアリングする可能性が低くなるため、これは靴下の数に依存する値になる可能性があります）、11に進みます。
残りをシャッフルする
1に移動
「インデックス」を忘れる
靴下を選ぶ
そのペアを見つける
靴下のペアがない場合は、「不足している」山に移動します
一致が見つかった場合はペアにし、ペアをパックして「一致した」パイルに移動します
それでもまだある場合は、1つの靴下が12になります
残りが1つしかない場合は、14に進みます
満足した笑顔:)

また、靴下を外したかのように、破損した靴下のチェックを追加することもできます。2から3の間、および13から14の間に挿入できます。

経験や訂正についてお聞きするのを楽しみにしています。

score 13 · Accepted Answer

パイルから靴下をペアリングするのがどれほど効率的かを言うには、最初にマシンを定義する必要があります。これは、通常、チューリングまたはランダムアクセスマシンのどちらによってもペアリングが行われないためです。アルゴリズム分析。

この機械

機械は、人間と呼ばれる現実世界の要素を抽象化したものです。一対の目で環境から読み取ることができます。そして、私たちのマシンモデルは、2本のアームを使用して環境を操作することができます。論理演算と算術演算は、私たちの脳を使用して計算されます（うまくいけば;-)）。

また、これらの機器で実行できるアトミック操作の固有の実行時間を考慮する必要があります。物理的な制約により、腕または目によって実行される操作は、一定ではない時間計算量を持ちます。これは、無限に大きな靴下の山を腕で動かすことも、無限に大きな靴下の上の靴下を目で見ることもできないためです。

しかし、機械物理学は私たちにもいくつかの良い点を与えてくれます。腕で靴下を動かすのはせいぜい1つに制限されていません。それらのカップル全体を一度に移動できます。

したがって、前の分析に応じて、次の操作を降順で使用する必要があります。

論理演算と算術演算
環境読み取り
環境の変更

靴下の数が非常に限られているという事実も利用できます。したがって、環境の変更には、山の中のすべての靴下が関係する可能性があります。

アルゴリズム

だからここに私の提案があります：

靴下をすべて床に広げます。
床の靴下を見てペアを見つけてください。
ペアが作成できなくなるまで2から繰り返します。
床に靴下がなくなるまで1から繰り返します。

靴下を床に広げると、一部の靴下が他の靴下を隠す可能性があるため、操作4が必要です。アルゴリズムの分析は次のとおりです。

解析

アルゴリズムは高い確率で終了します。これは、ステップ番号2で靴下のペアを見つけることができないという事実によるものです。

次の靴下のペアの実行時分析では、ステップ1の後nで、靴下の少なくとも半分が非表示になっていないと仮定します。したがって、平均的な場合、ペア2nを見つけることができます。n/2これは、ループがステップ4の実行O(log n)回数であることを意味します。ステップ2はO(n^2)何度も実行されます。したがって、次のように結論付けることができます。

アルゴリズムには、O(ln n + n)環境の変更が含まれます（ステップ1O(ln n)に加えて、床から靴下のすべてのペアを選択します）
アルゴリズムにはO(n^2)、ステップ2からの環境読み取りが含まれます
このアルゴリズムにはO(n^2)、ステップ2で靴下を別の靴下と比較するための論理演算と算術演算が含まれます。

したがって、実行時の全体的な複雑さは、妥当な量のソックスのO(r*n^2 + w*(ln n + n))場合r、wそれぞれ環境読み取りおよび環境書き込み操作の要因となります。2つの靴下が同じペアに属するかどうかを判断するには、一定量の論理積と算術演算が必要であると想定しているため、論理積と算術演算のコストは省略されています。これは、すべてのシナリオで実行可能であるとは限りません。

score 12 · Accepted Answer

私は、O（1）の時間を要するプロセスへの労力を減らすために、簡単な手順を実行しました。

入力を2種類の靴下（レクリエーション用の白い靴下、仕事用の黒い靴下）のいずれかに減らすことで、2つの靴下のどちらを手に持っているかを判断するだけで済みます。（技術的には、それらが一緒に洗浄されることはないため、プロセスをO（0）時間に短縮しました。）

望ましい靴下を見つけ、既存の靴下が不要になるように十分な量を購入するには、事前の努力が必要です。黒の靴下が必要になる前にこれを行っていたので、私の努力は最小限でしたが、走行距離は異なる場合があります。

このような先行作業は、非常に人気のある効果的なコードで何度も見られます。例には、円周率を小数点以下数桁に#DEFINEすることが含まれます（他の例もありますが、それが今頭に浮かぶものです）。

score 12 · Accepted Answer

靴下を並べ替えるときは、おおよその基数並べ替えを行い、同じ色/パターンタイプの他の靴下の近くに靴下を落とします。靴下を落とそうとしている場所またはその近くで完全に一致するものが見られる場合を除いて、その時点でペアを抽出します。

他のほとんどすべてのアルゴリズム（usrによる最高得点の回答を含む）は、並べ替えてからペアを削除します。人間としては、一度に検討する靴下の数を最小限に抑える方がよいと思います。

私はこれを行う：

特徴的な靴下を選ぶ（山の中で最初に目を引くものは何でも）。
その概念的な場所から基数ソートを開始し、その場所との類似性に基づいて靴下を山から引き出します。
新しい靴下を現在の山の近くに置き、その違いに基づいた距離を置きます。靴下が同じであるために別の靴下の上に置いていることに気付いた場合は、そこでペアを形成し、それらを取り外します。これは、将来の比較で正しい場所を見つけるための労力が少なくて済むことを意味します。

これは、O（1）時間であいまい一致する人間の能力を利用します。これは、コンピューティングデバイスでのハッシュマップの確立とある程度同等です。

特徴的な靴下を最初に引っ張ることで、そもそも特徴の少ない機能に「ズームイン」するスペースを残します。

フルーロカラーの靴下、縞模様の靴下、3足の長い靴下を削除すると、ほとんどが白い靴下になります。

ある時点で、靴下間の違いは他の人が違いに気付かないほど小さいので、それ以上のマッチングの努力は必要ありません。

score 11 · Accepted Answer

靴下を手に取るときはいつでも、一か所に置いてください。次に、手に取った靴下が最初の靴下と一致しない場合は、最初の靴下の横に置きます。もしそうなら、ペアがあります。このように、組み合わせがいくつあるかは実際には問題ではなく、靴下ごとに2つの可能性しかありません。つまり、靴下の配列にすでに一致しているものと一致していないもののどちらかです。配列内の場所に追加します。

これはまた、靴下が一致すると靴下が取り外されるため、靴下がすべて配列に含まれることはほぼ確実ではないことを意味します。

score 11 · Accepted Answer

サイズが「N」のハッシュテーブルについて考えてみます。

正規分布を仮定すると、少なくとも1つの靴下を1つのバケットにマッピングするための「挿入」の推定数はNlogNです（つまり、すべてのバケットがいっぱいです）。

私はこれを別のパズルの一部として導き出しましたが、間違っていることが証明されれば幸いです。これが同じブログ記事です

「N」は、あなたが持っている靴下のユニークな色/パターンの数のおおよその上限に対応します。

衝突（別名：一致）が発生したら、その靴下のペアを取り外すだけです。NlogNソックスの次のバッチで同じ実験を繰り返します。それの美しさは、人間の心の働き方のために、NlogN並列比較（衝突解決）を行うことができるということです。:-)

score 11 · Accepted Answer

靴下は、実際のものであろうと類似のデータ構造であろうと、ペアで提供されます。

最も簡単な答えは、ペアを分離する前に、左右の靴下へのポインタを含むペアの単一のデータ構造を初期化する必要があります。これにより、靴下を直接またはペアを介して参照できるようになります。靴下は、そのパートナーへのポインタを含むように拡張することもできます。

これは、抽象化レイヤーでそれを削除することにより、計算ペアリングの問題を解決します。

同じ考えを靴下のペアリングの実際の問題に適用すると、明らかな答えは次のとおりです。靴下のペアリングを解除しないでください。靴下はペアで提供され、引き出しにペアとして入れられ（おそらくそれらを一緒にボールでつなぐことによって）、ペアとして着用されます。しかし、ペアリングを解除できるのは洗濯機です。必要なのは、靴下を一緒に保ち、効率的に洗濯できる物理的なメカニズムだけです。

2つの物理的な可能性があります：

各靴下へのポインタを保持する「ペア」オブジェクトの場合、靴下をまとめるために使用する布製バッグを使用できます。これは大きなオーバーヘッドのようです。

しかし、靴下ごとに他の靴下への参照を維持するための適切な解決策があります。次のようなポッパー（またはアメリカ人の場合は「スナップボタン」）です。

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

次に、靴下を脱いで洗濯かごに入れた直後に靴下をスナップするだけで、靴下を「ペア」の概念の物理的な抽象化とペアリングする必要があるという問題が解消されます。

score 10 · Accepted Answer

この問題に何か新しいことを貢献できることを願っています。すべての答えが、全体的な洗濯性能を低下させることなく前処理を実行できる2つのポイントがあるという事実を無視していることに気づきました。

また、大家族でも靴下をたくさん想定する必要はありません。靴下は引き出しから取り出して着用し、洗濯する前にとどまる場所（たぶんビン）に投げ入れます。言われたビンをLIFOスタックとは呼びませんが、それを仮定するのは安全だと思います

人々は両方の靴下をビンのほぼ同じ場所に投げます。
ビンはどの時点でもランダム化されないため、
このビンの上部から取得されたサブセットには、通常、ペアの両方の靴下が含まれています。

私が知っているすべての洗濯機はサイズが限られており（靴下の数に関係なく）、実際のランダム化は洗濯機で行われるため、靴下の数に関係なく、常にほとんど含まれていない小さなサブセットがありますシングルトン。

私たちの2つの前処理段階は、「物干しに靴下を置く」と「物干しから靴下を取り出す」です。これは、清潔で乾燥した靴下を作るために行う必要があります。洗濯機と同じように物干しは有限で、靴下を置くライン全体が見えると思います。

put_socks_on_line（）のアルゴリズムは次のとおりです。

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

靴下を動かしたり、最適な靴下を探したりするのに時間を無駄にしないでください。これはすべてO（n）で行う必要があります。これは、靴下を分類せずにラインに配置するためにも必要です。靴下はまだペアリングされていません。ライン上にいくつかの類似性クラスターしかありません。ここに靴下のセットが限られていると、「良い」クラスターを作成するのに役立ちます（たとえば、靴下のセットに黒の靴下しかない場合、色によるクラスター化は適切ではありません）。

take_socks_from_line（）のアルゴリズムは次のとおりです。

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

残りのステップの速度を向上させるために、次の靴下をランダムに選ぶのではなく、各クラスターから靴下を順番に取っていくのが賢明であることを指摘しておく必要があります。どちらの前処理も、靴下をラインやバスケットに入れるよりも時間がかからないので、何をしなくても洗濯性能が大幅に向上します。

この後、ハッシュ分割アルゴリズムを実行するのは簡単です。通常、靴下の約75％はすでにペアになっており、靴下の非常に小さなサブセットが残っており、このサブセットはすでに（ある程度）クラスター化されています（前処理ステップの後、バスケットにエントロピーをあまり導入しません）。もう1つは、残りのクラスターは一度に処理できるほど小さい傾向があるため、クラスター全体をバスケットから取り出すことができるということです。

sort_remaining_clusters（）のアルゴリズムは次のとおりです。

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

その後、靴下は残りわずかです。ここで、以前にペアになっていない靴下をシステムに導入し、特別なアルゴリズムなしで残りの靴下を処理します。残りの靴下は非常に少なく、視覚的に非常に高速に処理できます。

残りのすべての靴下については、対応する靴下はまだ洗浄されていないと想定し、次の反復のためにそれらを片付けます。ペアになっていない靴下の成長を時間の経過とともに登録する場合（「靴下の漏れ」）、ビンを確認する必要があります。ランダムになる可能性があります（そこで眠る猫はいますか？）

私はこれらのアルゴリズムが多くの仮定をとることを知っています：ある種のLIFOスタックとして機能するビン、制限された通常の洗濯機、そして制限された通常の物干し-しかしこれはまだ非常に多くの靴下で機能します。

並列処理について：両方の靴下を同じビンに入れる限り、これらのすべての手順を簡単に並列化できます。

score 9 · Accepted Answer

パターンをハッシュとして使用して、比類のない靴下に使用されるハッシュテーブルを作成します。靴下を1つずつ繰り返します。靴下のハッシュテーブルのパターンが一致している場合は、靴下をテーブルから取り出してペアにします。靴下に一致するものがない場合は、テーブルに入れてください。

score 9 · Accepted Answer

n組の靴下を並べ替える際の問題はO（n）です。それらを洗濯かごに入れる前に、左のものを右のものに通します。それらを取り出すときに、スレッドを切り、各ペアを引き出しに入れます-2つのペアで2つの操作、つまりO（n）。

次の質問は、あなたが自分で洗濯をし、妻が洗濯をするかどうかということです。これは、まったく異なる問題領域で発生する可能性のある問題です。:)

score 9 · Accepted Answer

私は今靴下のペアリングを終えました、そしてそれをするための最良の方法は以下であることがわかりました：

靴下の1つを選択し、それを片付けます（そのペアの「バケツ」を作成します）
次のバケットが前のバケットのペアである場合は、既存のバケットに配置します。それ以外の場合は、新しいバケットを作成します。

最悪の場合、n / 2の異なるバケットがあり、どのバケットに現在の靴下のペアが含まれているかについてn-2の決定があることを意味します。明らかに、このアルゴリズムは、ペアが数個しかない場合にうまく機能します。私は12ペアでそれをしました。

それはそれほど科学的ではありませんが、うまく機能します:)

score 9 · Accepted Answer

「移動」操作がかなり高価で、「比較」操作が安価で、とにかくセット全体を元のストレージよりも検索がはるかに高速なバッファに移動する必要がある場合は、並べ替えを必須に統合するだけです。動く。

選別のプロセスを吊り下げから乾燥に統合することで、簡単にできることがわかりました。とにかく靴下を手に取って吊るす（動かす）必要があり、紐の特定の場所に吊るすのに費用はかかりません。バッファ全体（文字列）の検索を強制しないように、色/色合いで靴下を配置することにしました。左が暗く、右が明るく、正面がよりカラフルです。各靴下を掛ける前に、一致する靴下がすでにあるかどうか、つまり「スキャン」を他の2〜3個の靴下に制限している場合は、その「右側」を調べます。、もう片方をすぐ隣に吊るします。それから私はそれらをペアに丸め、乾いたら紐から外します。

これは、トップアンサーが提案する「色でパイルを形成する」とそれほど変わらないように見えるかもしれませんが、最初に、個別のパイルではなく範囲を選択することで、「紫」が「赤」または「青」のパイルになるかどうかを分類するのに問題はありません。それはちょうど間を行きます。そして、2つの操作（ぶら下げて乾かして並べ替える）を統合することにより、ぶら下げ中の並べ替えのオーバーヘッドは、個別の並べ替えの10％になります。

score 9 · Accepted Answer

O(n)私のソリューションは、正式には「余分な」スペースを必要とするため、要件に正確に対応していません。しかし、私の条件を考えると、それは私の実際のアプリケーションでは非常に効率的です。ですから面白いはずだと思います。

他のタスクと組み合わせる

私の場合の特別な条件は、乾燥機を使用せず、通常の布乾燥機に布を掛けるだけです。布を吊るすにはO(n)操作が必要であり（ちなみに、私はいつもここでビンパッキング問題を考えています）、その性質上、問題には線形の「余分な」スペースが必要です。バケツから新しい靴下を取り出すとき、ペアがすでにぶら下がっている場合は、ペアの横にぶら下げてみます。新しいペアの靴下の場合は、隣にスペースを残します。

OracleMachineの方が優れています;-)

一致する靴下がすでにどこかにぶら下がっているかどうかを確認するには、明らかに追加の作業が必要であり、コンピューターのO(n^2)係数を使用してソリューションをレンダリング1/2します。しかし、この場合、「人的要因」は実際には利点です。通常、一致する靴下がすでに吊るされている場合は、非常に迅速に（ほぼO(1)）特定できます（おそらく、知覚できない脳内キャッシングが含まれています）。Oracle Machineのように限定された「オラクル」;-)私たち人間には、デジタルマシンよりもこれらの利点がある場合があります;-)

ほぼ持ってい`O(n)`ます！

したがって、靴下のペアリングの問題と布の吊り下げの問題を結び付けると、O(n)無料で「余分なスペース」が得られ、時間のかかる解決策がありO(n)、単純な吊り布のペアよりも少し手間がかかり、すぐに完全なペアにアクセスできます。非常に悪い月曜日の朝でも靴下...;-)

score 8 · Accepted Answer

前処理はどうですか？すべてのペアが同じマーク/ID番号を持つように、すべての靴下にマークまたはID番号を縫い付けます。このプロセスは、新しい靴下を購入するたびに行われる可能性があります。次に、基数ソートを実行して、O（n）の総コストを取得できます。すべてのマーク/ID番号の場所を見つけて、すべての靴下を1つずつ選び、正しい場所に置きます。

score 7 · Accepted Answer

私は博士号（コンピュータサイエンス）のときにこれについてよく考えました。靴下を区別して正しいペアをできるだけ早く見つける能力に応じて、複数の解決策を考え出しました。

靴下を見て、その独特のパターンを覚えるコストはごくわずかであると仮定します（ε）。次に、最善の解決策は、単にすべての靴下をテーブルに投げることです。これには、次の手順が含まれます。

テーブルにすべての靴下を投げ（1）、ハッシュマップを作成します{パターン：位置}（ε）
靴下が残っている間（n / 2）：
1. ランダムな靴下を1つ拾う（1）
2. 対応する靴下の位置を見つける（ε）
3. 靴下（1）を取り出し、ペアを保管します

これは確かに最速の可能性であり、n + 1 = O（n）の複雑さで実行されます。しかし、それはあなたがすべてのパターンを完全に覚えていることを前提としています...実際にはそうではなく、私の個人的な経験では、最初の試みで一致するペアが見つからないことがあります。

すべての靴下をテーブルに投げます（1）
靴下が残っている間（n / 2）：
1. ランダムな靴下を1つ拾う（1）
2. ペアリングされていない場合（1 / P）：
  1. 同様のパターンの靴下を探す
  2. 靴下を取り、両方を比較します（1）
  3. よろしければ、ペアを保存します

これは、一致するペアを見つける能力に依存します。これは、非常によく似たパターンを持つダーク/グレーのペアまたは白いスポーツソックスを使用している場合に特に当てはまります。対応する靴下を見つける確率がPであることを認めましょう。ペアを形成するための対応する靴下を見つける前に、平均して1/P試行する必要があります。全体的な複雑さは1+（n / 2）*（1 + 1 / P）= O（n）です。

どちらも靴下の数は直線的であり、非常によく似たソリューションです。問題を少し修正して、セットに類似した靴下のペアが複数あること、および靴下の複数のペアを1回の移動（1 +ε）で簡単に保管できることを認めましょう。K個の異なるパターンの場合、以下を実装できます。

靴下ごとに（n）：
1. ランダムな靴下を1つ拾う（1）
2. パターンのクラスターに配置します
各クラスター（K）の場合：
1. クラスターを取り、靴下のペアを保管します（1 +ε）

全体的な複雑さはn+K = O（n）になります。それでも線形ですが、正しいアルゴリズムの選択は、PとKの値に大きく依存する可能性があります。しかし、靴下ごとにクラスターを見つける（または作成する）のが難しい場合があることに再び反対する人もいるかもしれません。

その上、あなたはまた、ウェブサイトを見て、最良のアルゴリズムが何であるかを見て、あなた自身の解決策を提案することによって時間を失うかもしれません:)

score 5 · Accepted Answer

パイルから靴下をペアリングするための効率的なアルゴリズムに向けて

前提条件

山には少なくとも1つの靴下が必要です
テーブルは、N / 2靴下（最悪の場合）を収容するのに十分な大きさである必要があります。ここで、Nは靴下の総数です。

アルゴリズム

試す：

最初の靴下を選ぶ
テーブルの上に置きます
次の靴下を選び、それを見てください（「これ以上靴下を山に入れない」例外をスローする可能性があります）
次に、テーブルの靴下をスキャンします（テーブルに靴下が残っていない場合は例外をスローします）
一致するものはありますか？a）はい=>一致する靴下をテーブルから削除しますb）いいえ=>靴下をテーブルに置きます（「テーブルが十分に大きくない」例外をスローする可能性があります）

それ外：

テーブルの大きさが十分ではありません。
ペアになっていない靴下をすべて慎重に混ぜ合わせてから、操作を再開します
。//この操作により、新しい山と空のテーブルが作成されます。
テーブルに靴下が残っていません：
投げる（最後のペアリングできない靴下）
靴下が山に残っていない：
洗濯室を出る

ついに：

まだ靴下が山にある場合：
goto 3

既知の問題点

周囲にテーブルがない場合、またはテーブル上に少なくとも1つの靴下を収容するのに十分な場所がない場合、アルゴリズムは無限ループに入ります。

改善の可能性

並べ替える靴下の数によっては、十分なスペースがあれば、テーブルで靴下を並べ替えることでスループットを向上させることができます。

これが機能するためには、靴下のペアごとに一意の値を持つ属性が必要です。このような属性は、靴下の視覚的特性から簡単に合成できます。

テーブルの靴下を上記の属性で並べ替えます。その属性を「色」と呼びましょう。靴下を一列に並べ、暗い色の靴下を右側に配置し（つまり、.push_back（））、明るい色の靴下を左側に配置します（つまり、.push_front（））。

巨大な山、特に以前は見られなかった靴下の場合、属性の合成にはかなりの時間がかかる可能性があるため、スループットは明らかに低下します。ただし、これらの属性はメモリに保持して再利用できます。

この可能な改善の効率を評価するには、いくつかの研究が必要です。次の質問が発生します。

上記の改善を使用してペアリングする靴下の最適な数はいくつですか？
与えられた数の靴下に対して、スループットが向上するまでに何回の反復が必要ですか？
a）最後の反復の場合
b）全体のすべての反復の場合

MCVEガイドラインに沿ったPoC ：

#include <iostream>
#include <vector>
#include <string>
#include <time.h>

using namespace std;

struct pileOfsocks {
    pileOfsocks(int pairCount = 42) :
        elemCount(pairCount<<1) {
        srand(time(NULL));
        socks.resize(elemCount);

        vector<int> used_colors;
        vector<int> used_indices;

        auto getOne = [](vector<int>& v, int c) {
            int r;
            do {
                r = rand() % c;
            } while (find(v.begin(), v.end(), r) != v.end());
            v.push_back(r);
            return r;
        };

        for (auto i = 0; i < pairCount; i++) {
            auto sock_color = getOne(used_colors, INT_MAX);
            socks[getOne(used_indices, elemCount)] = sock_color;
            socks[getOne(used_indices, elemCount)] = sock_color;
        }
    }

    void show(const string& prompt) {
        cout << prompt << ":" << endl;
        for (auto i = 0; i < socks.size(); i++){
            cout << socks[i] << " ";
        }
        cout << endl;
    }

    void pair() {
        for (auto i = 0; i < socks.size(); i++) {
            std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);
            if (it != unpaired_socks.end()) {
                unpaired_socks.erase(it);
                paired_socks.push_back(socks[i]);
                paired_socks.push_back(socks[i]);
            }
            else
                unpaired_socks.push_back(socks[i]);
        }

        socks = paired_socks;
        paired_socks.clear();
    }

private:
    int elemCount;
    vector<int> socks;
    vector<int> unpaired_socks;
    vector<int> paired_socks;
};

int main() {
    pileOfsocks socks;

    socks.show("unpaired socks");
    socks.pair();
    socks.show("paired socks");

    system("pause");
    return 0;
}

score 5 · Accepted Answer

多くの著者が指摘しているように、基数ソートは靴下をソートする効率的な方法です。まだ提案されていないのは、完全なハッシュ方法です。靴下の各ペアが購入された時間を使用すると、そのようなハッシュです。靴下を購入するときに順番に番号を付けるだけで、山を通り抜けるときに、番号の付いた引き出しに靴下を置くことができます。

最大24足の靴下の例。より大きな靴下コンパートメントは、靴下を一緒に巻く必要性、いわゆる速度/保管のトレードオフを排除することに注意してください。

score 3 · Accepted Answer

私の提案する解決策は、色を除いてすべての靴下の細部が同一であることを前提としています。靴下間で延期する詳細がある場合は、これらの詳細を使用して、私の例では色の代わりにさまざまな種類の靴下を定義できます。

靴下が山積みになっていることを考えると、靴下には青、赤、緑の3色があります。

次に、色ごとに並列ワーカーを作成できます。対応する色を塗りつぶすための独自のリストがあります。

At time i:

Blue  read  Pile[i]    : If Blue  then Blue.Count++  ; B=TRUE  ; sync

Red   read  Pile[i+1]  : If Red   then Red.Count++   ; R=TRUE  ; sync

Green read  Pile [i+2] : If Green then Green.Count++ ; G=TRUE  ; sync

同期プロセスあり：

Sync i:

i++

If R is TRUE:
    i++
    If G is TRUE:
        i++

これには初期化が必要です。

Init:

If Pile[0] != Blue:
    If      Pile[0] = Red   : Red.Count++
    Else if Pile[0] = Green : Green.Count++

If Pile[1] != Red:
    If Pile[0] = Green : Green.Count++

どこ

Best Case: B, R, G, B, R, G, .., B, R, G

Worst Case: B, B, B, .., B

Time(Worst-Case) = C * n ~ O(n)

Time(Best-Case) = C * (n/k) ~ O(n/k)

n: number of sock pairs
k: number of colors
C: sync overhead

score 3 · Accepted Answer

2つの考え方、一致を見つけるのにかかる速度と、ストレージと比較したすべての一致を見つけるのにかかる速度。

2番目のケースでは、すべての一致についてソックスにクエリを実行するGPU並列バージョンを指摘したいと思います。

一致するプロパティが複数ある場合は、簡単にするために、グループ化されたタプルとより洗練されたzipイテレータ、および推力の変換関数を使用できます。ただし、ここでは単純なGPUベースのクエリを使用します。

//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>

// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator          GpuListIterator;

template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
    ColoredSockQuery( int colorToSearch )
    { SockColor = colorToSearch; }

    int SockColor;

    __host__ __device__
    bool operator()(T x)
    {
        return x == SockColor;
    }
};


struct GenerateRandomSockColor
{
    float lowBounds, highBounds;

    __host__ __device__
    GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};

    __host__ __device__
    int operator()(const unsigned int n) const
    {
        thrust::default_random_engine rng;
        thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
        rng.discard(n);
        return dist(rng);
    }
};

template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
    typedef typename std::iterator_traits<GpuListIterator>::value_type T;

    std::cout << name << ": ";
    thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    int numberOfSocks = 10000000;
    GpuList socks(numberOfSocks);
    thrust::transform(thrust::make_counting_iterator(0),
                      thrust::make_counting_iterator(numberOfSocks),
                      socks.begin(),
                      GenerateRandomSockColor(0, 200));

    clock_t start = clock();

    GpuList sortedSocks(socks.size());
    GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
                                                     socks.end(),
                                                     sortedSocks.begin(),
                                                     ColoredSockQuery<int>(2));
    clock_t stop = clock();

    PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);

    double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
    std::cout << "Time elapsed in ms: " << elapsed << "\n";

    return 0;
}

    //nvcc -std=c++11 -o test test.cu

1000万靴下の実行時間：9ミリ秒

score -3 · Accepted Answer

靴下の1つのペアをキー自体として抽象化し、他のペアを値として抽象化できる場合は、ハッシュを活用できます。

床にあなたの後ろに2つの架空のセクションを作成します。1つはあなた用、もう1つはあなたの配偶者用です。
靴下の山から1つ取ってください。
次に、以下のルールに従って、靴下を1つずつ床に置きます。
- 靴下を自分のものとして識別し、床の関連するセクションを見てください。
- 床でペアを見つけることができる場合は、それを拾い上げて結び上げるか、クリップで留めるか、ペアを見つけてバスケットに入れてから何でもします（床から取り外します）。
- 関連するセクションに配置します。
すべての靴下が山からなくなるまで3を繰り返します。

説明：

ハッシュと抽象化

抽象化は、ユーザーエクスペリエンス（UX）を向上させるために使用されてきた非常に強力な概念です。コンピューターとの実際の相互作用における抽象化の例には、次のものがあります。

場所に移動するために実際のアドレスを入力する代わりに、アドレスにアクセスするためのGUI（グラフィカルユーザーインターフェイス）でのナビゲーションに使用されるフォルダーアイコン。
さまざまなレベルの音量、ドキュメントのスクロール位置などを制御するために使用されるGUIスライダー。

私は靴下を複製することができないので、ハッシュまたは他のインプレースではない解決策はオプションではありません（できればそれは素晴らしいかもしれませんが）。

靴下のどちらかのペアが入るスロットを配置する前に知っておく必要があるように、質問者はハッシュを適用することを考えていたと思います。

そのため、床に置かれた1つの靴下をハッシュキー自体として抽象化することを提案しました（したがって、靴下を複製する必要はありません）。

ハッシュキーを定義する方法は？

以下のキーの定義は、同様の靴下が2つ以上ある場合にも機能します。つまり、2組の黒人男性用靴下PairAとPairBがあり、各靴下の名前は、PairA-L、PairA-R、PairB-L、PairB-Rであるとします。したがって、PairA-LはPairB-Rとペアリングできますが、PairA-LとPairB-Lをペアリングすることはできません。

靴下は、次のように一意に識別できるとしましょう。

Attribute[Gender] + Attribute[Colour] + Attribute[Material] + Attribute[Type1] + Attribute[Type2] + Attribute[Left_or_Right]

これが最初のハッシュ関数です。これには短い表記を使用しましょうh1(G_C_M_T1_T2_LR)。h1（x）はロケーションキーではありません。

Left_or_Right属性を削除する別のハッシュ関数はですh2(G_C_M_T1_T2)。この2番目の関数h2（x）は、ロケーションキーです。（あなたの後ろの床のスペースのために）。

スロットを見つけるには、h2（G_C_M_T1_T2）を使用します。
スロットが見つかったら、h1（x）を使用してハッシュを確認します。それらが一致しない場合は、ペアがあります。それ以外の場合は、靴下を同じスロットに入れます。

注：ペアが見つかったら削除するため、一意のh2（x）またはh1（x）値を持つスロットは最大で1つだけであると想定しても問題ありません。

一致するペアが1つだけの靴下がある場合は、h2（x）を使用して場所を見つけます。ペアがない場合は、ペアであると見なすのが安全なので、チェックが必要です。

靴下を床に置くことが重要なのはなぜですか

靴下を積み重ねるシナリオを考えてみましょう（最悪の場合）。これは、ペアを見つけるために線形探索を行う以外に選択肢がないことを意味します。

それらを床に広げると、より多くの視認性が得られ、一致する靴下を見つける可能性が高くなります（ハッシュキーと一致します）。手順3で靴下を床に置いたとき、私たちの心は無意識のうちに場所を登録していました。-したがって、この場所がメモリ内で利用可能である場合、一致するペアを直接見つけることができます。-場所が記憶されていない場合でも、心配する必要はありません。そうすれば、いつでも線形検索に戻ることができます。

ペアを床から取り外すことが重要なのはなぜですか？

短期間の人間の記憶は、覚えておくべき項目が少ない場合に最もよく機能します。したがって、ペアを見つけるためにハッシュに頼る可能性が高くなります。
また、ペアの線形検索が使用されている場合に検索されるアイテムの数が減ります。

分析

ケース1：ハッシュ手法を使用して、デルピナが床の靴下を直接覚えたり見つけたりできない最悪のケース。Derpは、フロア上のアイテムを線形検索します。これは、ペアを見つけるためにパイルを反復処理するよりも悪くはありません。
- 比較の上限：O（n ^ 2）。
- 比較のための下限：（n / 2）。（1つおきの靴下Derpinaが拾うときは、前の靴下のペアです）。
ケース2：Derpは、床に置いたすべての靴下の場所をそれぞれ覚えており、各靴下には正確に1つのペアがあります。
- 比較の上限：O（n / 2）。
- 比較のための下限：O（n / 2）。

私は比較操作について話しているのですが、山から靴下を選ぶのは必然的にn回の操作になります。したがって、実際の下限は、n/2の比較を伴うn回の反復になります。

物事をスピードアップ

DerpがO（n / 2）の比較を取得するように完全なスコアを達成するには、Derpinaに次のことをお勧めします。

靴下に慣れるために、より多くの時間を靴下に費やしてください。はい、それはダープの靴下にももっと時間を費やすことを意味します。
グリッド内のペアを見つけるようなメモリゲームをプレイすると、短期記憶のパフォーマンスが向上する可能性があり、これは非常に有益です。

これは要素の区別の問題と同等ですか？

私が提案した方法は、要素の識別性の問題を解決するために使用される方法の1つであり、ハッシュテーブルに配置して比較を行います。

正確なペアが1つしかないという特殊なケースを考えると、これは要素の個別の問題と非常によく似ています。靴下を並べ替えて、隣接する靴下のペアを確認することもできるので（EDPの別のソリューション）。

ただし、特定の靴下に複数のペアが存在する可能性がある場合は、EDPから逸脱します。

algorithm - どうすれば靴下をパイルから効率的にペアリングできますか？

37 に答える 37

この機械

アルゴリズム

解析

他のタスクと組み合わせる

OracleMachineの方が優れています;-)

ほぼ持っていO(n)ます！

パイルから靴下をペアリングするための効率的なアルゴリズムに向けて

Related

Reference

ほぼ持ってい`O(n)`ます！