問題タブ [knuth]

私のデータ構造の理解があまり良くないので、私の質問がばかげているように聞こえたら申し訳ありません。

私はクヌースのダンシングリンクアルゴリズムについて読んでいて、それが基本的にどのように機能するかをほぼ理解しています。ダンスリンクのデータ構造の視覚化は、列と行があり、各セルが上、下、左、右のセルに接続されたテーブルのように見えると言われています。また、このアルゴリズムでは循環二重リンクリストが使用されていることも読みました。

私が知りたいのは、二重リンクリストを列と行を含むそのようなテーブルにどのように正確に作成できるかということです。

私が知っているように、ほとんどの二重リンクリストには2つのポインター（上と下）しかありませんが、4つのポインター（上、下、左、右）を持つ独自のカスタムリンクリストを作成する必要があるということですか？または他の方法がありますか？

前もって感謝します。

要素間の比較の最小数を使用して、Pythonで5つの要素のリストを並べ替える実行プランをモデル化する必要があります。それ以外は、複雑さは関係ありません。

結果は、別のときにリストをソートするために必要な比較を表すペアのリストです。

7つの比較（要素間、常に、複雑さに関してではない）でこれを行うアルゴリズムがあることは知っていますが、読み取り可能な（私にとって）バージョンを見つけることができません。

7つの比較で5つの要素を並べ替え、その並べ替えの「実行プラン」を作成するにはどうすればよいですか。

PD：宿題ではありません。

C で gettimeofday() 関数を使用して乱数ジェネレーターを作成しました。ここで、Knuth によって開発された統計的または経験的な方法を使用してこれを評価する必要があります。同じものを徹底的に検索しましたが、実行可能な解決策が見つかりませんでした。または、私が間違っているかもしれません。上記の基準に従ってこの RNG を評価するのを手伝ってください。

私は C++ の課題を抱えており、選択したコンテナーに関する Knuth 問題の単純な解決策を考案し、生成されたパフォーマンス データを調査する必要があります。以下の問題を参照してください。

異なる名前を持つ 300 万人の男性が、ニューヨークからカリフォルニアに至るまで、端から端まで敷設されました。各参加者には一枚の紙が渡され、その紙に自分の名前と列のすぐ西側にいる人の名前を書き留めました。列の最西端にいた男性は、何をすべきかわからなかったので、紙を捨てました。残りの 2,999,999 枚の紙片は巨大なバスケットに入れられ、ワシントン DC の国立公文書館に運ばれました。ここでバスケットの内容は完全にシャッフルされ、磁気テープに移されました。

この時点で、情報科学者は、元の順序で人々のリストを再構築するのに十分な情報がテープにあることに気付きました。そしてコンピューター科学者は、テープのシーケンシャル アクセスと少量のランダム アクセス メモリのみを使用して、データ テープを 1000 回未満のパスで再構成する方法を発見しました。これはどのように可能でしたか？

[言い換えると、1 ≤ i < N のペア (xi, xi+1) がランダムな順序で与えられ、xi が異なる場合、シーケンス x1 x2….xN をどのように取得し、すべての操作をシリアル手法に制限することができますか? 、磁気テープでの使用に適しています。これは、指定された 2 つのキーのどちらが他のキーよりも先行しているかを簡単に判断できない場合に、順序をソートする際の問題です。

調査の結果、リストや法線マップではなく、unordered_map を使用することにしました。私が理解していないのは、コードとして実装するために提供された単純なソリューションです。

論文が (Name, Name) タプルの集まりであると考えてください。これらのタプルから、後継者 (西側の隣人) と前任者 (東側の隣人) の両方を確立できます。

私の最初の質問 - xc はコンテナの性質上順序を決定できないため、単なるランダムな要素ですか?

私の 2 番目の質問 - 私たちが与えられた名前は次のようなファイルにあります:

それで、最初の名前を1つのリストに入れ、次に姓を別のリストに入れる必要があるという素朴な解決策はありますか?

私が完全にオフになっている場合は申し訳ありませんが、私はこれを本当に理解しようとしました!

事前にこの質問をご覧いただきありがとうございます。

次のアイテムのリストを注文しようとしています。

次の順序に：

これは次の方法で行われます。

1. 最初のペアを取り、名前をリストに入れる
2. ペアの2番目の名前を使用して、それが1番目の名前として使用されているペアを見つけます
3. そのペアの2番目の名前をリストに追加します
4. 2と3を繰り返す

unordered_mapにペアを入力してから、各名前を並べ替えてリストに追加しています。これは、次のコードで確認できます。

注：最初の値しか挿入されていないため、現時点で「push_front」が正しいかどうかはわかりません。

私の質問は、誰かが私がこれについてどうやって行くことができるかについて私にいくつかの洞察を与えることができるかということです。私は最善の方法と私の考えが正しいかどうかわからないので。任意の洞察をいただければ幸いです。

knuthBendix を大量の書き換えルールに適用しようとしています。したがって、私はそれを異なるセットで並行して機能させようとしています。

例として、私は実行しようとします：

を使用してコンパイルしghc -threaded、経由で実行し+RTS -Nます。他のアルゴリズムを並行して実行すると、機能します。しかし、knuthBendix の場合はそうではありません。

誰かが解決策を知っていますか？

ありがとう、フランツ

配列をランダム化するために knuth shuffle を使用しています。別の配列を追加して、同じ方法でランダム化できるようにしたいと思います。['A|1|I,B|2|II,C|3|III,D|4|IV']などのように、文字列内で配列を分離することを以前に考えていました。

stackoverflow でこれを読みましたが、knuth シャッフル用に配置する方法がわかりません。

これは、最初の配列から文字列を取得するために現在使用している JS であり、追加のコードは上記のリンクから取得されます。

JavaでKnuths Mastermind Algorithmを実装しようとしています。このアルゴリズムについては、この論文 paper で説明されています。これは私がこれまでに実装した方法ですが、アルゴリズムが必要とするよりも最大5回以上の推測が必要です。

スコアリング メソッドや getMax メソッドなどの他のメソッドが意図したとおりに機能すると仮定すると、なぜこれが機能しないのでしょうか?