有限のミッション プールからユーザーのミッションを抽出するアプリケーションを構築しています。問題は、私が欲しいということです:
私の問題を要約すると、プールから最も一般的でないミッションを抽出する必要があります。
誰かが、最も一般的でないもの (LFU) を見つける既知のアルゴリズムを参照してください。理論的な側面も必要なので、これに関する記事や研究論文 (Scientific American などの有名な雑誌から) を誰かが知っていれば、それは素晴らしいことです。
最も使用頻度の低いミッションを取得するには、すべてのミッションに使用回数をカウントするカウンターを設定します。次に、カウンター値が最も低いミッションを検索します。
友人のグループによって最も頻繁に使用されなかったミッションを取得するために、すべてのユーザーについて、そのユーザーが実行したミッション (および回数) を保存できます。とにかく、この情報はおそらく役に立ちます。次に、ユーザーのために新しいミッションを選択する必要がある場合、ユーザーとそのすべての友人が使用したミッションとその頻度の (一時的な) 結合リストを簡単に作成し、頻度で並べ替えることができます。これはそれほど高価ではありません。
あなたの2つの要件に基づいて、「最も使用されていない」ミッションがこれと何の関係があるのかわかりません。あなたは繰り返しのない任務が欲しいと言いました。
オプション1：
すべてのミッションを保持するためにどのコンテナを使用しますか？あなたまたはあなたの友人がミッションを選択したとき、それがリストであると仮定し、そのミッションをリストの最後に移動します（そこにあるミッションと交換します）。これで、最初のリストが2つのサブリストに分割されました。最初の部分は未使用のミッションを保持し、2番目の部分は使用済みのミッションを保持します。2つのリストを分離するピボット/インデックスを追跡します。
これで、あなたやあなたの友達が新しいミッションを選択するたびに、最初のサブリストから選択されます。次に、それを2番目のサブリストに移動し、ピボットを更新します。
オプション2： 最終的にミッションを繰り返すが、最初に選択された時間が最も少ないものを選択する場合は、コンテナーを最小ヒープにすることができます。各ミッションに使用カウンターを追加し、それに基づいてヒープに追加します。ミッションを抽出し、その使用カウンターをインクリメントしてから、ヒープに戻します。これは良い解決策ですが、プログラムの単純さによっては、循環バッファーを使用することもできます。
あなたが構築しているものについてもっと知っておくといいでしょう:)
必要な構造はmin-heapだと思います。O(Log(n)) で最小値を抽出でき、O(Log(n)) でアイテムの値を増やすこともできます。
良いスタートは、一般的なグラフでの完全な最小マッチングのための Edmond Blossom V アルゴリズムです。二部グラフがある場合は、フロイド-ワーシャル アルゴリズムを探して最短経路を見つけることができます。トポロジー検索も使用できるかもしれませんが、これらのアルゴリズムは習得が非常に難しいためわかりません。