問題タブ [combinatorics]

最終的な目標はアルゴリズムを考案することですが、これはそれ自体がプログラミングの問題ではありません。参考文献、または少なくともゲームの種類の名前を探しています。テレビのゲーム番組でかなり広まっています。ゲームは次のとおりです。

多数のスロットがあり、各スロットには (ある有限セットからの) アイテムが含まれていますが、それはわかりません。各スロットに何が含まれているかを推測する必要があります。ジャッジ (各スロットに何が含まれているかを知っている) に推測を伝えると、ジャッジはどれが正しいかは言わずに、いくつの推測が正しいかを教えてくれます。すべてのアイテムの推測に成功すると、ゲームは終了します。

このタイプのゲームに関する情報には、可能性が最も低い推測で解決するためのアルゴリズムへの参照など、興味があります。Google で検索できるように名前だけでも構いません。

ありがとう！

まず、ウィキペディアでの問題の名前は「集合の分割」です。

可能なパーティションをカウントするアルゴリズムがあります。それをスピードアップするために、私はキャッシュを使用します：

さらに、これらの可能なパーティションのリストを表示する別のアルゴリズムがあります。ただし、まだキャッシュを使用していないため、非常に低速です。

だから私は2つの質問があります：1）2番目のアルゴリズムにもキャッシュを実装することは可能ですか？はいの場合、これを行うのを手伝っていただけませんか。2）2番目のアルゴリズムの結果を文字列ではなく構造化配列に書き込むことは可能ですか？

あなたが私を助けてくれることを願っています。事前にどうもありがとうございました！

PS：simonnとDan Dyerの2つの機能に感謝します！

代入問題は単一の行列の形で提起できるので、NumPy にそのような行列を解く機能があるかどうか疑問に思っています。これまでのところ、私は何も見つけていません。NumPy/SciPy に代入問題解決機能があるかどうか知っている人がいるでしょうか?

編集:その間、 http: //software.clapper.org/munkres/ で Python (NumPy/SciPy ではない) の実装を見つけました。それでも、NumPy/SciPy の実装ははるかに高速になると思いますよね?

文献があるかどうかわからないコスト最適化のリクエストがあります。説明するのが少し難しいので、質問が長くなってしまうことをあらかじめお詫びします。

このように機能する私がアクセスしているサーバーがあります：

• リクエストはレコード (r1, ...rn) とフィールド (f1, ...fp) に対して行われます
• デカルト積 (r1, ..., rp) x (f1,...fp) のみを要求できます
• このようなリクエストに関連するコスト (時間とお金) は、リクエストのサイズに比例します。

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

b=1一般性を失うことなく (正規化するだけで)、コストは次のようになると仮定できます。

T((r1, ...,rn)x(f1,...fp)) = a + n * p

• ユーザーからのリクエストである、ペアのサブセットをリクエストするだけで済み(r1, f(r1)), ... (rk, f(rk))ます。私のプログラムは、ユーザーとサーバー (外部) の間の仲介者として機能します。このようなリクエストがたくさんあります (1 日に数万件)。

グラフィカルに、これを nxp スパース行列と考えることができます。そのために、非ゼロの値を四角形の部分行列でカバーしたいと考えています。

持つ：

• コストが一定であるため妥当に保たれている部分行列の数
• すべての「x」は部分行列内にある必要があります
• 線形コストのため、カバーされる総面積が大きすぎてはなりません

私の問題のスパース係数を g と名付けます (可能なペアの総数に対する必要なペアの数g = k / (n * p). 私は係数を知っていaます .

明らかな観察結果がいくつかあります。

• a が小さい場合、最善の解決策は各 (レコード、フィールド) ペアを個別に要求することであり、総コストは次のようになります。k * (a + 1) = g * n * p * (a + 1)
• a が大きい場合、最良の解決策はデカルト積全体を要求することであり、総コストは次のとおりです。a + n * p
• 2番目のソリューションはすぐに優れていますg > g_min = 1/ (a+1) * (1 + 1 / (n * p))
• もちろん、デカルト積の順序は重要ではないため、行列の行と列を転置して、より簡単にカバーできるようにすることができます。次に例を示します。

次のように並べ替えることができます

そして、求める最適解がある(f1,f3) x (r1,r3) + (f2) x (r2)

• 組み合わせ論が爆発するため、すべてのソリューションを試して低コストを探すことは選択肢ではありません。

だから私はおおよその解決策を探しています。私はすでに、マトリックスを指定してカバーを見つけるある種の貪欲なアルゴリズムを持っています(ユニタリセルで始まり、マージ内の空のセルの割合がしきい値を下回っている場合はそれらをマージします)。

いくつかの数字を覚えておくと、私の n は 1 から 1000 の間のどこかで、私の p は 1 から 200 の間のどこかです。レコードは、要求されたフィールドが類似しているクラスにあるため、実際には「ブロック状」です。残念ながら、レコードのクラスにアクセスできません...

質問 1 : アイデア、巧妙な単純化、または有用な論文の参考文献を誰かが持っていますか? 多くのリクエストがあるので、平均してうまく機能するアルゴリズムを探しています (ただし、n と p が大きい場合に行列全体をリクエストするなど、極端なケースではうまく動作しない余裕はありません)。 、そしてリクエストは実際には非常にまばらです）。

質問 2 : 実際、問題はさらに複雑です: コストは実際には次のような形式です: a + n * (p^b) + c * n' * p'、ここで、b は定数 < 1 です (レコードがフィールドを要求されると、他のフィールドを要求するのはそれほどコストがかかりません。フィールド) でn' * p' = n * p * (1 - g)あり、要求したくないセルの数です (それらは無効であり、無効なものを要求するには追加コストがかかるため)。この問題を迅速に解決できるとは夢にも思いませんが、それでも...誰かアイデアはありますか?

1 から 25 までの数字があり、15 の数字のセットを選択する必要があるとしましょう。

可能なセットは、私が正しければ 3268760 です。

これらの 3268760 のオプションのうち、たとえば 100000 を生成する必要があります

そのサブセットの 100000 個の一意でランダムなものを生成する最良の方法は何でしょうか?

それを行う方法、アルゴリズムはありますか？

そうでない場合、重複を検出するための最良のオプションは何ですか?

私はPHPでこれを行うことを計画していますが、一般的な解決策で十分であり、あまり「学術的」（より実用的）ではない参照があれば、大いに役立ちます。

文字列の特定の組み合わせから6以下の長さのすべての単語を取得することを含む組み合わせ論の割り当てがありました。

この場合、それはS = {'a'、'ab'、'ba'}でした。教授はそれらをリストアップし始めたばかりですが、プログラムを使えばもっと簡単に解決できると思いました。唯一の問題は、すべての可能なオプションを実際に計算する優れたアルゴリズムを取得できないことです。

誰か助けていただければ幸いです。私は通常Pythonでプログラミングしますが、実際にはアルゴリズムの助けが必要です。

n 個の要素があります。例として、7 つの要素、1234567 としましょう。7 つあることはわかっています。= これらの 7 つの要素の可能な 5040 順列。

2 つの関数で構成される高速なアルゴリズムが必要です。

f(数値) は、0 から 5039 までの数値を一意の順列にマップし、

f'(permutation) は、順列を生成元の数値にマップします。

各順列に独自の番号がある場合、番号と順列の対応は気にしません。

したがって、たとえば、次のような関数があるかもしれません

頭に浮かぶ最速のアルゴリズムは、すべての順列を列挙し、両方向のルックアップ テーブルを作成することです。テーブルが作成されると、f(0) は O(1) になり、f('1234567') は文字列のルックアップ。ただし、これは特に n が大きくなるとメモリを消費します。

メモリの欠点がなく、すばやく動作する別のアルゴリズムを提案できる人はいますか?

次のような属性を持つデータセットがあります。

など。そのような変数は約200あります。

一度に1つの値で、属性の組み合わせを生成するアルゴリズムが必要です。

言い換えれば、私の最初の組み合わせは次のようになります。

次のセットは次のようになります。

各属性の各値を属性自体として扱い、単純な組み合わせジェネレーターを使用しようとしました。相互に排他的な選択肢が組み合わせに含まれており、可能な組み合わせの数が非常に多かったため、機能しませんでした（正確には、133873417996074857185490633899939406700260683726864088366400）

アルゴリズム（できればJavaでコーディングされたもの）を提案していただけますか？

ありがとう！！

アイテムのリストを取得し、リストを正確に 2 つのサブリストに分割した結果として得られる一意のサブセットをすべて生成する効率的なアルゴリズムを見つけようとしています。これを行う一般的な方法があると確信していますが、特定のケースに興味があります。リストはソートされ、重複するアイテムが存在する可能性があります。

いくつかの例：

入力
{1,2,3}

出力
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}

入力
{1,2,3,4}

出力
{{1},{2,3,4}}
{{2},{1,3,4}}
{{3},{1,2,4}}
{{4},{1,2, 3}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}

入力
{1,2,2,3}

出力
{{1},{2,2,3}}
{{2},{1,2,3}}
{{3},{1,2,2}}
{{1,2},{2, 3}}
{{1,3},{2,2}}

私はこれを紙の上で行うことができますが、プログラムで行う簡単な方法を見つけるのに苦労しています. 特定のコード例ではなく、これを行う方法の簡単な疑似コードの説明のみを探しています。

どんな助けでも大歓迎です。ありがとう。

アルゴリズムだけでは解決できないこの問題を抱えています。

ビデオ フレームを常に固定レート F (1 秒あたり 30 フレームとしましょう) でキャプチャするビデオ キャプチャがあるとします。

私が望むのは、このフレーム シーケンスを n 個 (たとえば 4 個) のサブシーケンスに「分割」することです。各サブシーケンスにはフレームレート fn があり、明らかに < F です。サブシーケンス内のフレームは時間的に等間隔に配置されているため、たとえば、有効な 10 fps シーケンス f1 は、F = 30 fps および時間 = 1 秒の場合のように構築されます。

(0 はサブシーケンスに属さないフレームで、1 はサブシーケンスに属するフレームです):

また

または、F = 30 および f = 8 の場合:

(そして、「1」で 1 秒が再開するまでに MCD (30,8) = 120 フレームかかります)。

問題は、サブシーケンスが衝突できないことです。したがって、F=30、f1 = 10 fps (3 フレームごと)、f2 = 5 fps (6 フレームごと) の場合、このシーケンスは問題ありません。

しかし、f3 = 6 fps を追加すると

また

3 番目のサブシーケンスは最初のサブシーケンスと衝突します。

質問は：

• 衝突せず、等間隔になる n (n <= 4) サブシーケンスのフレームレートのすべての組み合わせを見つける方法はありますか?

（一般的なケースが必要ですが、この特定のケースでは、1つのシーケンスのみ（自明）のすべての有効な組み合わせ、2つのシーケンスのすべての有効な組み合わせ、3つのシーケンスのすべての有効な組み合わせ、および4つのシーケンスのすべてが必要です） .

誰かが私の心を啓発してくれることを願っています。ありがとうございました！