2

だから私はこれを数時間解決しようとしてきましたが、どうやらまだ何かが欠けているようです. たぶん私は間違った方法で考えていますが、それは非常に複雑な問題だと思います:

項目が固定された 3 つのリストがあります。問題を説明するために、アイテムが異なる位置にある可能性があるいくつかの例外を除いて、アイテム A から Z がほとんど同じ順序で含まれていると仮定します。また、すべてのアイテムを含むリストは 1 つだけです。もう 1 つのリストにはサブセットが含まれており、特定のアイテムが欠落しています。この問題の解決策は十分であるため、すべてのアイテムを含むリストを作成せず、セットの一部のみを重複させることも可能です。複数（> 3）のリストで問題を解決するアルゴリズムはさらに優れています。

例を次に示します。

List 1: A B C D E F G H I J
List 2: A C D B F G
List 3: B C D E H F G

ここで、これら 3 つのリストを照合して、並べ替え順序が異なる場所と欠落しているアイテムを視覚化する必要があります。したがって、結果は次のようになります。

List 1: A B C D   E   F G H I J
List 2: A   C D B     F G
List 3:   B C D   E H F G

したがって、リスト 2 の B が間違った位置にあり、リスト 3 には A がなく、H も間違った位置にあることがすぐにわかります。

結果をCSVに保存してExcelにインポートすることを考えていました。したがって、行は次のとおりです。

A,A,
B,,B
C,C,C
...

ここで私の質問は、CSV 出力を生成する方法でリストを一致させるにはどうすればよいですか? 私が使っている言語は Java です。これまでのところ、参照リスト以外のリストに以前の項目が含まれていて、それが参照リストの後半に表示されるという問題で失敗しました。

ちなみに、これは現実世界の問題です。

任意の提案をいただければ幸いです。

4

2 に答える 2

3

Unixツールなど、この問題を解決するための既製のツールがありますdiff3。ヒューリスティックの開発に多くの時間を費やす意思がない限り、任意の数のリストについてそれを解決しようとすることはお勧めできません。これは、最長共通部分列問題のNP困難な一般的なケースを扱っているためです。

于 2013-02-01T11:44:42.483 に答える
1

私があなたの質問を正しく理解していれば、あなたは基本的に、バイオインフォマティクス内でよく研究されているトピックである複数配列アラインメントの問題を解決しようとしています. それにはいくつかのアルゴリズムがあり、そのうちのいくつかはレーベンシュタイン距離の概念に基づいています(問題の2つの配列バージョンを解決します)-そこから始めることをお勧めします.

于 2013-02-01T11:48:21.410 に答える