24

私のガールフレンドはインタビューでこの質問を受けました. 私はそれがとても好きだったので、それを共有したいと思いました... 辞書 (単語の配列) を受け取るアルゴリズムを書きます. 配列は辞書順でソートされますが、abc の順序は何でもかまいません。たとえば、z、y、x、..、c、b、a などです。または、完全にめちゃくちゃになる可能性があります: d、g、w、y、... すべての abc 文字を含める必要さえなく、最終的には文字である必要はまったくありません。文字列を形成する任意の記号である可能性があります。たとえば、5、α、!、@、θ で構成されている可能性があります。文字が何であるかを発見するのはあなたのアルゴリズム次第です (簡単な部分)。

アルゴリズムは、シンボルの正しい辞書式順序を返す必要があります。

注/考慮事項: 1. 特定の辞書について、常にすべての文字の完全な順序を見つけることができますか? 単語が 1 つしかなく、記号が 1 つ以上ある辞書を考えてみましょう... 2. 辞書にエラーがないことを想定することはできません。アルゴリズムは、辞書に矛盾が含まれているかどうかを判断し、エラーがあることを出力する必要があります。3. ヒント: シンボル間の関係を表すのに適したデータ構造を考えてください。これにより、問題がはるかに簡単になります。

おそらく明日、解決策を投稿します。決してそれが最も効率的だと主張しているわけではありません。他の人の考えをまず見てみたい。質問をお楽しみください

PSソリューションを投稿するのに最適な形式は疑似コードを使用することだと思いますが、これはあなたの考慮に任せます

4

4 に答える 4

34

これは、有向非巡回グラフでのトポロジカル ソートです。最初にグラフを作成する必要があります。頂点は文字であり、辞書順で一方が他方よりも小さい場合にエッジがあります。トポロジー順序が答えを与えてくれます。

矛盾は、有向グラフが非巡回でない場合です。一意性は、多項式時間でテスト可能なハミルトニアン パスが存在するかどうかによって決まります。

グラフの作成

これを行うには、辞書にある 2 つの連続する「単語」をそれぞれ比較します。次の 2 つの単語が次々に現れるとします。

x156@
x1$#2z

次に、この場合、最も長い一般的なプレフィックスを見つけ、x1このプレフィックスの直後に続く文字を確認します。この場合、 と が5あり$ます。5単語は辞書にこの順序で表示されるため、 は辞書式に より小さくなければならないと判断でき$ます。

同様に、次の単語が与えられた場合（辞書に次々と表示されます）

jhdsgf
19846
19846adlk

'j' < '1'最初のペア (最も長い一般的なプレフィックスは空の文字列) からわかります。2 番目のペアは、有用なことを何も教えてくれません (1 つは別のプレフィックスであるため、比較する文字がないため)。

ここで、後で次のように表示されるとします。

oi1019823
oij(*#@&$

次に、このペアが'1' < 'j'.

トポロジカルソート

トポロジカル ソートを行う従来の方法は 2 つあります。アルゴリズム的に単純なのは深さ優先検索アプローチで、 fromxからyifへのエッジがありy < xます。

アルゴリズムの擬似コードはウィキペディアで提供されています。

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no incoming edges

function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from n to m do
            visit(m)
        add n to L

for each node n in S do
    visit(n)

上記のアルゴリズムが完了すると、リストLにはトポロジー順に頂点が含まれます。

一意性のチェック

以下はウィキペディアからの引用です。

トポロジカル ソートに、ソートされた順序で連続する頂点のすべてのペアがエッジで接続されるというプロパティがある場合、これらのエッジは DAG で有向ハミルトニアン パスを形成します。ハミルトニアン パスが存在する場合、トポロジの並べ替え順序は一意です。パスの端を尊重する他の順序はありません。逆に、トポロジカル ソートがハミルトン パスを形成しない場合、DAG は 2 つ以上の有効なトポロジカル順序を持ちます。この場合、エッジで接続されていない 2 つの連続する頂点を交換することにより、2 番目の有効な順序を形成することが常に可能です。お互いに。したがって、一意の順序付けが存在するかどうか、およびハミルトニアン パスが存在するかどうかを多項式時間でテストできます。

したがって、順序が一意であるかどうかを確認するには、L(上記のアルゴリズムから) の 2 つの連続する頂点すべてが直接エッジで接続されているかどうかを確認するだけです。そうであれば、その順序は一意です。

複雑さの分析

グラフが作成されると、トポロジカル ソートは になりO(|V|+|E|)ます。一意性チェックは ですO(|V| edgeTest)。ここで、edgeTestは 2 つの頂点がエッジで接続されているかどうかをテストする複雑さです。隣接行列では、これはO(1)です。

グラフの作成には、ディクショナリの 1 回の線形スキャンのみが必要です。単語がある場合W、それは ですO(W cmp)。ここで、cmpは 2 つの単語を比較する複雑さです。常に 2 つの後続の単語を比較するため、必要に応じてあらゆる種類の最適化を行うことができますが、それ以外の場合は単語の長さがO(L)どこにあるかという単純な比較になります。L

アルファベットなどについて十分な情報があると判断したら、辞書の読み取りを短絡することもできますが、単純な構築ステップでさえO(WL)、辞書のサイズである が必要です。

于 2010-06-26T10:51:10.890 に答える
3

シンボルの合計順序を見つけたいとします。

1) 合計注文数を常に決定できるとは限らないことは明らかです。

2) 有向非巡回グラフを使用して、シンボル間の半順序を表すことができます。各文字は、グラフ内で 1 回だけ表されます。連続する単語のすべてのペアの同じ位置にあるすべての文字のペアを見て、それを設定します。グラフで作成したサイクルは、ディクショナリのエラーを示しています。a->d、a->b、b->d のような関係のセットを a->b->d にフラット化します。最終的に得られるのが、1 つのソース (前任者のない文字) と 1 つのシンク (後続者のない文字) を持つグラフである場合、アルファベットのように全順序があります。

于 2010-06-26T10:55:43.960 に答える
2

ウィキペディアで提案されている他のアルゴリズムを使用してこれを解決しました。ウィキペディアの疑似コードは次のとおりです。

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

パスを見つけるためのより「常識的な」アプローチを提供すると思います（つまり、グラフを見てパスを見つけなければならない場合にどのように解決するか）。それでも、polygenelubricants によって提案された深さ優先のアプローチには利点がありません (コメントで提案されているようにサイクル検出コードを追加した場合)。答え

于 2010-06-26T12:55:10.650 に答える
1

あなたは単語の配列で辞書を持っています、そして私はこのデータ構造を使うことを提案します、なぜならそれは十分に良くそして変換に時間がかかるからです。

あなたは文字の正しい順序を見つけたい、

C1、C2、C3、C4、...、Cn

辞書にm個の単語があります。（Ci、Cj）のような一連のルールがあると便利です。これは、Ci <= Cjであることを意味します。ここで、i、jは正の自然数であり、i <m、j<mです。一連のエラーが発生するはずです

Vは膨大な数であり、m * mより大きいため、私の意見では次のようになります。

foreach i = 1, m do
    foreach j = i + 1, m do
        findFirstDifferenceInTheWords
        /*charI is the first difference in Wi from Wj and charJ is the first difference in 
          Wj*/
        if (Wi <> Wj)
            if (Wi contains Wj or Wj contains Wi) == false
            charSet.add(charI, charJ)
        else if k exists and the following is true ((i < k < j) and (Wi <> Wk))
            error.addIfDoesntExist("paradox", Wi)
        else
            error.addIfDoesntExist("redundant", Wi)
        end_if
    end_foreach
end_foreach

l個のルールが見つかりました

foreach i = 1、l do foreach j = i + 1、l do if charSet.exists（charI、charJ）and charSet.exists（charJ、charI）error.add（ "paradox Relation"、charI、charJ）

この後、charI = charJは（charI、charJ）と（charJ、charI）の両方がセットに存在し、charI <= charJが唯一のルールであり、その逆ではないと見なすことで、語順を構築できます。そのcharI<charJ。

結論：「<=」は数論では完全で適切な順序の関係であるため、「<=」の関係を使用する方が「<」の関係を使用するよりも優れています。「<」は適切な順序です。注：charI<charJまたはcharI= charJの場合、出力は正しく表示される必要があります。たとえば、次の表記を使用できます。characters（C1C2C3、C4、C5C6、...）ここで、C1 = C2 = C3 <C4 <C5 = C6 .. ..

これがお役に立てば幸いです。

もちろん、WjにWiが含まれている場合、そこからルールを抽出することはできません。

于 2010-06-26T14:15:25.273 に答える