問題タブ [lexicographic]

最初に値でソートし、次に別の値でソートすることになっている次の operator< があります。

これは正しくなく、メンバー変数に対して 3 番目の比較テストを行わないと実行できないと感じていますが、これが機能しない例は見つかりません。では、これは本当に期待どおりにソートされるのでしょうか? ありがとう

編集：私はそれを次のようにコーディングしたでしょう：

違いはありますか？私の経験からは正しいが、最初のものよりも長いことを知っているので、私は尋ねています

実装方法に興味がstd:next_permutationあったので、バージョンを抽出しgnu libstdc++ 4.7、識別子とフォーマットをサニタイズして、次のデモを作成しました...

出力は期待どおりです：http：//ideone.com/4nZdx

私の質問は次のとおりです：それはどのように機能しますか？i、、jの意味は何kですか？彼らは実行のさまざまな部分でどのような価値を持っていますか？その正しさの証明のスケッチは何ですか？

明らかに、メインループに入る前に、些細な0または1要素リストのケースをチェックするだけです。メインループのエントリで、iは最後の要素（1つ過ぎた端ではない）を指しており、リストは少なくとも2要素の長さです。

メインループの本体で何が起こっているのですか？

質問を投稿するのはこれが初めてです。だから私は宿題プログラムに取り組んでいて、誰かがチャイムを鳴らして私を助けてくれることを願っているいくつかのことに少し行き詰まっています. プログラムで行う必要があるのは次のとおりです。

• プログラムは、句読点のある文を含むファイルを読み込む必要があります。
• 文を単語と句読点に解析します。
• 単語は辞書に入力され、句読点はリストに入力されます。単語を辞書に追加するとき、大文字と小文字は無視されます。辞書は辞書順に保存されていることに注意してください。
• 辞書とリストの各エントリには、単語または句読点が元のテキストに出現する回数がカウントされます。
• テキストを読んだ後 ($ の最初の文字を含む行でテキストが終了します)、辞書を出力し、カウントをリストします。
• 次に、プログラムは次のような形式の行を読み取ります: word1 < word2
• これは、テキスト内の word1 を word2 に置き換えることを意味します

ファイル（hw5-input）を入力して辞書順で印刷し、大文字を取り除きました。単語数もありますが、単語数で別々の行に印刷することはできません..私はまだまた、単語を交換してファイルを再度印刷する必要がありますが、単語カウントで印刷することは本当に助けが必要です。これが私がこれまでに持っているものです：

入力ファイル (hw5-input) は次のとおりです。

次のように次の行にアルファベット順に印刷する必要があります。

私は少し混乱しています。辞書式順序で順列を生成する問題は、並べ替えの問題とどのように異なりますか？誰かが例を挙げて説明してもらえますか？ありがとう

Java Strings の辞書順でソートされたリストがあり、[s1,s2,s3,s4, ...., sn]UTF-8 encoding を使用して各文字列をバイト配列に変換すると、バイト配列bx = sx.getBytes("UTF-8")のリスト[b1,b2,b3,...bn]も辞書順でソートされますか?

vb6 を扱う前にこの種の質問をしたことはわかっていますが、遅すぎたため、この仕事には C# を使用することにしました。同じコードが 2 倍の速度で実行されるようになりましたが、それでも遅すぎます。

遅い理由は、すべての行をチェックする各列の終わりから辞書式ソートを開始するためです。

これを高速化すると信じているのは、最初の列からすべての行をチェックしてソートプロセスを開始し、その列の最初のバイトごとに最下位の行を検出し、同じ最初の下位バイトを持つ複数の行を検出し、次のステップのためにそれらをグループ化する場合ですこれは、2 番目の (次の) 列をチェックし、2 番目のバイトのどちらが最下位バイトであるかを調べます。それらが両方とも同じである場合は、次の列に移動します。次の行のバイトが異なる場所を検出すると、列コードが実行されます。最初のバイトと2番目に低いバイトを見つけることに進みます..実際には、このプロセスが適切な速度向上を得るために機能するはずだと思っていました.. .

現在のコードは、すべての行を並べ替える最後の列から力ずくで並べ替えることによって機能します。次に、1 つの列を左に移動し、すべての行を再度並べ替えます。最初の列に到達して並べ替えるまで、これを繰り返します。明らかな理由もなく反復を行うため、これは遅いです。

256 列と 256 行、合計 65,536 の配列要素があるとします。現在のコードを使用すると、各行が適切な並べ替え順序になるまで、各行を複数回並べ替える必要があるとします。列ごとに 65,536 回の反復が必要になる可能性があります。したがって、関数を呼び出すたびに、合計で 256*65536 = 16,777,216回の反復が見積もられます。これが実際に遅い理由です。

私はこれを求めることがたくさんあることを知っていますが、誰かが自由な時間を持っていて、おそらく以前にこれをやったことがあれば、私を助けてくれることに感謝します.

ここに私がこれまでに作業しなければならないコードがあります。

これは私の最初のスレッドです。

このコードは、スウェーデン語から英語への用語集テスト用です。

問題があり(*it).engelska)ます ! そして、なぜ私(*it).engelskaはこのコードで使用できないのですか?

よろしくお願いします！

たとえば。2つの文字列2と10がある場合、辞書式順序で注文すると10が最初になります。

非常に些細な解決策は、文字をn回繰り返すことです。

しかし、これを行うためのよりエレガントな方法はありますか？

I'm writing lexicography software, which may theoretically need to sort tens of thousands of strings with arbitrary (dictionary-project-specific) collations. There are two means of specifying custom collations:

1. a map of graphemes to unicode-style multi-level collation keys.
2. an array of alphabetic graphemes (possibly including digraphs, etc.) in sorting order, which can be internally transformed into a map of collation keys.

The naive method of comparing strings is to check grapheme-by-grapheme until you find a mismatch, and then look up the collation keys for the mismatched graphemes to compare, but I'm hoping there's a more efficient way of doing it.

The best idea I've got so far depends on noticing that strings of equal length can be treated as little-endian base-n numbers, so I can pre-compute an integer key for each string which turns collation into cheap integer comparison. But, this breaks for strings of different length (a big deal when sorting a dictionary), and there's no bound on the size of integers that could be generated. To account for length differences, I thought I could compute a list of keys for all prefixes of each string, and then just compare the keys for prefixes of length equal to the shorter string being compared. That seems to do pretty well, but key sizes are still unbounded, and storing the keys could use a lot of memory.

Is there a way to improve that approach? Or am I just going about it entirely wrong, and there's a much better means of sorting strings with arbitrary collations?

マージする簡単な行列（またはdf）が2つあります。

問題ありません：列1でソートした後、列1は0から15まで上手く昇順で出力されます。

しかし、待ってください。2つの列（両方とも数値）をマージすると、並べ替え順序が突然アルファベットのように見えます。

ええと、グロス。どうしたの？そして、私は何をしますか？