問題タブ [partition-problem]

Postgres に大きなテーブルがあります。

テーブル名は次のとおりbigtableで、列は次のとおりです。

category_id の modulo 10 と capture_time 列の日付部分でテーブルを分割しました。

パーティション テーブルは次のようになります。

where 句で category_id と capture_time を使用してクエリを実行すると、パーティションが期待どおりにプルーニングされません。

category_id%10=0ただし、 where句に正確なモジュロ基準（ ）を追加すると、完全に機能します

すべてのクエリにモジュロ条件を追加することなく、パーティションのプルーニングを正しく機能させる方法はありますか?

n のすべてのパーティションのセットから無作為に選択された整数パーティションの共役も、一様ランダム サンプルですか? 私の結果は、長さ s の n のランダムなパーティションを迅速に生成するためには励みになりますが、そうすべきかそうでないかを説明することはできません。

ところで、私の結果は 1.) 特定の長さ (s) の小さい n (<70) のすべてのパーティションを生成する 2.) 各パーティションの分散をマクロ状態記述子として計算する 3.) カーネルを比較する小さなランダム サンプル (つまり、長さが s に一致するか共役長が s に一致する n のランダムに生成された 500 個未満のパーティション) に対する実行可能なセット全体 (長さ s の n のすべてのパーティション) にわたる分散の密度曲線。ランダム サンプルのカーネル密度曲線は、実行可能なセット全体 (つまり、一致する n 個の s のすべてのパーティション) の曲線とよく一致します。これは、大部分が共役パーティションであるランダム サンプルが、n および s ベースの実行可能セットのパーティション間の分散の分布をキャプチャすることを視覚的に示しています。見た目どおりに機能する理由を説明することはできません。

注: ランダム サンプルを生成する他の多くの手順では、明らかに偏ったサンプル (つまり、形状が異なり、非常に重複しないカーネル密度曲線) が生成されます。

関連する質問:

• 数値のリストを 2 つの等しい合計リストに分割するアルゴリズム
• リストを 2 つの部分に分割し、それらの合計が互いに最も近くなるようにします

2k正確に要素を含むリストがあるとしましょう。ここで、それを 2 つの部分に分割します。各部分の長さは ですが、部分kの合計ができるだけ等しくなるようにします。

簡単な例: [3, 4, 4, 1, 2, 1]に分割される可能性が[1, 4, 3] and [1, 2, 4]あり、差額の合計は1

ここで、パーツが任意の長さを持つことができる場合、これは分割問題のバリエーションであり、弱いことがわかっています。NP-Complete.

しかし、リストを等分に分割することに関する制限(常にkとであるとしましょう2k) は、この問題を多項式時間で解決できるようにしますか? それに対する証拠はありますか（またはそれがまだであるという事実の証明スキームNP）？

したがって、次のような配列があるとしましょう。

配列をこのようなものに分割する便利な方法はありますか?

私は同様の質問を調べましたが、ほとんどの人がscipyのようにポイントをクラスター化するために k-means を使用することを提案しましたが、これは私のような初心者にとっては非常に混乱します。また、2次元以上のクラスタリングにはk-meansの方が適していると思いますよね？数値に応じて、N 個の数値の配列を多くのパーティション/クラスタリングに分割する方法はありますか?

厳格な範囲分割を提案する人もいますが、常に結果が期待どおりにレンダリングされるとは限りません

方程式があります: 1a + 2b + 3c + 4d ... + 9i = 9

制約: 1 <= a + b + c + ... + i <= 10 ⁴

ここで、a、b、..、iは非負の整数で、各整数には特定の範囲があります。

例: 1 <= a <= 5、2 <= b <= 3など。

これらの変数の異なる値のセットの数、または単にその方程式を解く方法の数を見つける必要があります。

これを解決する再帰的な方法がありますが、それは非常に遅いです。与えられた制約の下でこれを効率的に解決する方法を考えることができません。

これが問題です：

同じ長さの2つの配列AとBがあります。次のように、それらを2つのグループPとQに分割する必要があります。（1）それらの差が最小化される。（2）A [i]がPまたはQのいずれかに入る場合、B[i]は別の中に入る必要があります。

実際の問題へのリンクは次のとおりです。http：//opc.iarcs.org.in/index.php/problems/EQGIFTS

これが私の論理です（実際の問​​題を解決するため）：

入力がabcdefgの場合、値のリストとa、b、c、d、e、fのインデックスはそれぞれ0、1、2、3、4、5です。

tがa、b、c、d、e、f、gのインデックスである場合、プログラムは次のようにtとiをチェックします。 = 1であり、iの値を1増やし、tの値を1減らします。

一致するものが見つかるとすぐに、両方のインデックスの値を交換し、[t-1]から始まる値を並べ替えます。結果の値のリストが出力になります。

このアルゴリズムの何が問題なのかはわかりませんが、すべてのテストケースで間違った答えが返されます。私はそれが動的計画法を使用して解決できること、そしてそれがパーティション問題のバリエーションであることを知っています。しかし、この問題を解決するためにパーティションアルゴリズムを変更する方法がわかりません。

matlabにMinCUTアルゴリズムがあります。機能です！メールファイルから呼び出すにはどうすればよいですか。すべての変数を定義する必要がありますか？または、入力のみを定義する必要がありますか？

整数のリストのすべてのパーティションを見つけるにはどうすればよいですか? ほとんどの場合、SML で実装するので、再帰を使用するアルゴリズムが必要です。アルゴリズムだけが必要です。コーディング部分は自分で行います。誤ってサブセットを見つけるためのコードを書きましたが、これを行う時間があまりありません

SML はパスカルと似たようなものなので、フォーマットのコツをつかむことができます。例えば階乗で書くと、このような楽しい fuc x = if x<0 then 0 else if x=1 then 1 else x*(fac x-1)

前もって感謝します

バランス パーティションの問題を実装し、バックポインターを使用してサブセットの要素を取得したいと考えています。

バックポインターについて質問があります。

MIT の Dynamic Programming Practice Problems Nr.の助けを借りて。7 とこのサンプル コードを使用して、Processing で動作するプログラムを取得することができました (私はプログラミング初心者なので...)。

ここで、両方のサブセットの要素を取得できるようにしたいと考えています。

MIT Video では、これは「バックポインターを維持する標準的なトリックを使用して」達成できると説明されています。

これを行う方法を知っている人はいますか？

私はいくつかのアルゴリズムプログラミングの問題に取り組んできましたが、1つについて質問があります。問題は、この質問で参照されているものと同じです。USACO：サブセット（非効率的）

高Nには遅すぎるいくつかの（動的ではない）ソリューションをコーディングすることができました。少しごまかして、オンラインでいくつかのソリューションを検索する必要がありました。高速アルゴリズムは簡単ですが、答えを知っていても、問題から答えに至る方法がわかりません。等しい合計のサブセットが形成される方法でパターンを見ることができますが、それらのパターンとアルゴリズムソリューションの間のリンクはわかりません。

問題（上記のリンク）は次のとおりです。

1からN（1 <= N <= 39）までの連続する整数のセットが与えられた場合、合計が同じである2つのサブセットにセットを分割できる方法はいくつありますか？たとえば、{1,2,3}は一方向に分割できます：{1,2}{3}。

より大きなセットの場合、答えは0（N *（N + 1）/ 2が奇数の場合）であるか、次の単純なアルゴリズムによって与えられます。

繰り返しになりますが、アルゴリズムがどのように機能するかを確認できます。printステートメントを挿入したので、アルゴリズムがどのように機能するかを「見る」ことができます。アルゴリズムの操作が、2セットのパーティションが生成されるさまざまな方法のパターンにどのようにリンクしているかがわかりません。

リンクされた質問の回答は関連があるかもしれませんが、それがどのように機能するかを接続することもできません：「これは多項式（x ^ 1 + 1 / x）（x ^ 2 + 1 / x ^ 2）...（x ^ n + 1 / x ^ n）。..。 "

誰かが私との関係を明確にしたり、この特定の問題を説明するいくつかの参考資料を教えてもらえますか？ありがとう。