8

可変数の要素を持つリストがいくつかあります。各リストはソートされていますが、ソートのアルゴリズムは不明です。リストを、すべてのリストを同じ順序で、重複することなく含む 1 つの大きなリストにマージしたいと思います。

入力例:

  1. XS、M、L、XL
  2. S、M、XXL
  3. XXS、XS、S、L

期待される結果：

  • XXS、XS、S、M、L、XL、XXL

期待される結果は、次のように、各入力シーケンスの要素を正しい順序で含むマージ結果を取得するために、入力シーケンスを照合することによって取得されます。

    XS   M L XL
       S M      XXL
XXS XS S   L
-------------------
XXS XS S M L XL XXL

あいまいな位置を持つ要素がある場合、関数は通知する必要があります。ここでは、XXL (M、L、または XL の後に残る可能性があります) になり、XL の後にその位置を手動で指定する必要があります (ここでは、並べ替えアルゴリズムを知っていて、役立つ可能性があるため)。元のリストのように、各ペアを順番に 2 つの要素ごとにペアを定義することを考えました。これから、完全なリストを作成できます。

4

4 に答える 4

6

部分的に順序付けられたセットまたはポーズセットをマージしようとしています。マージのあいまいな部分はアンチチェーンと呼ばれます。したがって、ポーズセットをマージし、アンチチェーンが何であるかを知らせるアルゴリズムが必要です。

これは、ポーズセットをマージしてアンチチェーンを検出するためのアルゴリズムを説明する論文です。また、最初の著者に連絡して利用可能なソースコードがあるかどうかを確認したい場合に備えて、最初の著者のホームページへのリンクもあります。

于 2013-06-20T16:26:32.020 に答える
3

これが私がすることです：

  1. リストを前処理します: XXS が XS よりも小さいことを理解することは、S がよりも小さいことを理解することです... XXL は [制約充足問題](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem) です。このタイプの問題には、元のリストで定義された制約が与えられたすべての要素の中から正しい順序を探すことが含まれます。
  2. ステップ 1 を実行した後、セット {XXS, ..., XXL} からセット {1, ..., 6} への双方向マッピングを作成します。
  3. リストごとに、2 で定義したマッピングを使用して別のリストを作成します。
  4. [マージ ソート](http://en.wikipedia.org/wiki/Merge_sort) を変更して、2 つのリストを結合します。マージ アルゴリズムを変更して、比較される 2 つのアイテムが同一である場合に報告するようにします (マージされるアイテムの 1 つを無視します)。
  5. リストが 1 つになるまで、リストのペアごとに手順 4 を実行します。
  6. 2 で定義したマッピングを使用して、リストのテキスト バージョンを作成します。
于 2011-01-10T21:03:36.643 に答える
-1

ソート部分については、あなたの説明によると、Merge Sort で十分だと思います。入力配列の最初の要素が結果配列と同じである場合、入力配列の要素をスキップする必要があります。

私の理解が正しければ、考えられる入力要素全体の合計順序を構築する必要があります。一部の半順序は入力配列で既に定義されていますが (既にソートされているため)、ユーザーが指定する必要があるものもあります。たとえば、質問では、順序

'S'<'M'<'XXL'

'XS'<'M'<'L'<'XL'

'XXS'<'XS'<'S'<'L'

明確に定義されています。しかし、アルゴリズムは、「XXL」が「XL」、「L」よりも大きいか小さいかをまだ知りません。
3 つの入力配列が並べ替えられているため、入力要素の全体的な順序が存在する必要があります。したがって、私の提案は、可能なすべてのデータ要素の順序付きリストをデータ プロバイダーに依頼することです。ばかげているように聞こえますが、それは簡単な方法です。

このリストが利用できない場合、対処する簡単な方法は、ユーザーにペアの並べ替えを求めるプロンプトを表示し、アルゴリズムがあいまいなペアに遭遇したときに、これが既存の入力シーケンスと競合するかどうかを確認し、それを覚えておくことです。トポロジ ソートは、このアプリケーションよりも強力だと思います。単一のデータ要素を扱うため、総順序が存在する必要があります。トポロジの並べ替えは半順序を処理するためのものです。

于 2013-06-26T21:39:05.940 に答える