だから私はそのような問題を抱えています.2つの「サブ配列」に均等に分散された1から10までのいくつかの整数で構成されるk個のタプルがあります(したがって、1 2 3 4 5 <=> 6 7 8 9 10、例）。私がやりたいのは、最初の行に常に一緒に表示されるようなペア (2 要素の組み合わせ、配置は関係ありません) があるかどうかを見つけることです (同じ側にあり、隣接しているかどうかは関係ありません) 。後の行 (たとえば、上記の例では、(1,2) は常に一緒に表示されるため、2 番目の入力行として 3 4 2 8 1 <=> 5 6 7 9 10 もある場合、条件は true になります。 (3,4) など - ただし、そのようなペアは 1 つあれば十分です. また、5 は 4 の反対側にあるため、(4,5) 結婚は 2 行目で破られました)。
最初の組み合わせ配列を作成するのに時間がかかりすぎるべきではありませんが、「クロス配列」の 2 要素組み合わせテーブルを構築する代わりに、「ペア」が壊れているかどうか (一方の側で見つからない) を確認するより速い方法はありますか?入ってくるすべての行を調べてから、そこからのすべての要素を既に構築された最初のペアと比較しますか? このサウンドは非常に遅く、控えめに言っても n^2 です。誰にもアイデアはありますか？他に方法が思いつきません。
編集と修正:わかりました、申し訳ありませんが、私の非公式の説明は、軽く言えば、混乱を招くようです :) ここで、より正式な内容を説明します。問題の内容が明確になることを願っています。
入力としてそれぞれ k 個の整数の l 行が与えられます。各行は、{1, 2, ..., k} シーケンスの順列で構成されています。各行の最初の k/2 整数を「左」側として扱い、他の整数を「右」側として扱います。任意の選択された線について、それらが常に同じ側 (左または右) にあるような整数 x、y はありますか? 4 - 1 2 は、1 2 と 3 4 が常に一緒であるため、結婚を満たします (左に 1 回、右に 1 回)。
2番目の編集私の頭をもう少し割った後、組み合わせを力ずくで比較するという考えはまったく無意味に思えます。k=100,000 があるとします。すると、最初の行の入力のみの後、ほぼ 25 億の要素を管理する必要があります。次に、2 行目で同様の桁数の配列を構築し、すべての比較を交差させて実行することを想像してください。 2行目以降は結婚していないことが確実です。恐ろしく時間がかかりますよね？
どういうわけか両側の列を合計することを考えましたが、これによりアルゴリズムが左右に依存します（つまり、1 2 - 3 4 は 4 3 - 2 1 とは異なりますが、そうではありません）...実際、私のアイデアはすべて終了しますサイド依存です。それを使って何ができるでしょうか？