問題タブ [lexicographic]

各エントリが整数のペアで構成される、m行と列を持つ行列が与えられます。行列にペアが 2 回現れることはありません。n(a,b)

ここで、これらのペアを並べ替えたいと思います。同じ行にある2 つのペア(a,b)とについて、そのペアが の左側にあるようにします。さらに、同じ列にある 2 つのペアの場合、 の場合に限り、それが以下になります。(c,d)(a,b)(c,d)((a < c) or (a=c and b < d))(a,b)(c,d)(a,b)(c,d)((b < d) or (b=d and a < c)

すべての行と列が上記の条件を満たす配置を見つけた場合、それを安定と呼びます。

最初にすべてのペアを列の状態に従って並べ替えると、安定した配置が得られやすくなりますが、これにはO(mn log(mn))時間がかかります。次に、このリストを m 個の部分に分割しますp_1,...,p_m(それぞれが n 個の要素で構成され、それぞれ(a,b)の in p_i、(c,d)in p_jit isで構成されます(a,b) < (c,d) if i < j)。p_iここで、各パーツを列条件に従ってソートします。これは、パーツO(n log(n))ごと、つまりO(mn log(n))すべてのパーツに対して行われます。ソートされた部分p_iを列に書き込むとi、安定した配置が得られます。

ここで、特殊なケースm=nを考えてみましょうN=n²。上記の引数を使用すると、安定した配置が時間内に取得できることがわかりO(N log(N))、上限が得られます。さて、これは疑問を投げかけます：

この問題の下限は? O(N log(N))最適ですか？

CLP(FD) を使用して、BProlog で辞書式順序制約を実装しようとしています。

マニュアルからわかる限り、BProlog は組み込みのlexLeq制約を提供していません (ただし、このグローバルな制約には効率的な伝播アルゴリズムが存在します)。バイナリ制約:

制約を表現するには、 s(A1 #/\ A2 #/\ ... #/\ AN) => AN+1を具体化できるはずだと思うので、次のようにします。Ai

次に、s を収集Bし、接続詞が有効であることを確認するには、次のようにします。

このアイデアは、次の (おそらく非常に醜い) コードにつながります。

これは部分的に機能します：

生成されたすべてのソリューションが制約を満たしていることがわかります。問題は、すべての有効なソリューションが生成されるとは限らないことです。私が説明した制約は、それX1 #>= X2 #>= ... #>= XNまたはそのようなものを何らかの形で暗示しているように見えるため、すべての変数は または のいずれ0かですが、上記のクエリはvsまたはvsなど1のソリューションも返す必要があります。[0,1,0][0,1,0][0,0,0][0,1,0]

それで、私の推論に何か問題がありますか、それとも上記の定義にバグがありますか?

文字列からすべての重複を削除し、可能な限り辞書編集的に最小の文字列を選択します。たとえば、文字列 cbacdcbc は adcb ではなく acdb を返します。

したがって、辞書編集的に最小の文字列を選択する必要がない場合、これは比較的単純な解決策になりますが、その事実を考慮すると、効率的な解決策にたどり着く方法がわかりません。これが私がこれまでに持っているものです：

宿題があり、大部分は完了しましたが、ある時点で立ち往生しています。二分木を検索してキーワードを見つけなければなりません。キーワードが表示されない場合は、検索したいキーワードを接頭辞として持っているツリーで、辞書的に次の文字列を見つけなければなりません。以前の基準。

次のコードは、正確な単語が見つからなかった後に検索するためのものです。

例

私が言葉を持っているなら：ツリートラバーサルツリー

私が検索した場合：「tr」

私はトラバーサルだけを返します。

トラバーサルの原因が葉であるために左右に移動できず、木や木も表示する方法が見つかりません。

私はいくつかのことを試しましたが、うまくいかなかったので、今あなたに尋ねています。さらに、辞書編集上の次のキーワードの処理方法や、それをどうする必要があるのか​​もわかりません!

どんな助けでも大歓迎です！:D

コードは正常に機能していますが、非常に非効率的です。
問題を解決するためのより時間効率の良い方法はありますか?