問題タブ [data-partitioning]

n (たとえば 3 人) と s (たとえば 100$ ) が与えられた場合、s を n 人に分割したいと思います。

したがって、合計が s になるすべての可能な n タプルが必要です。

以下の私のScalaコード：

これは n の値が小さい場合に機能します。( n=1、2、3 または 4)。

n=4 を超えると、非常に時間がかかり、実質的に使用できなくなります。

遅延評価/ストリームを使用してコードを作り直す方法を探しています。

私の要件：nから10まで動作する必要があります。

警告 : 問題は非常に急速に大きくなります。Matlab からの私の結果 -

xorがゼロである整数のパーティションの数を計算する効率的な方法を探しています。F（n、c）=＃{（x1、x2、...、xc）| x1 + x2 + ... + xc = n＆x1 xor x2 xor ... xor xc = 0}

nとcの値が小さい場合、ネストされたループを実行してこれらの値を計算するのは簡単です。しかし、より大きな値の場合、それは扱いにくいです。動的計画法を可能にする閉じた形または少なくとも再帰式を取得したいのですが。

それぞれに与えられた値が等しいかほぼ等しくなるように、それぞれ独自のドル値を持つ48個のアイテムを3つの継承者のそれぞれに配布するにはどうすればよいですか？

これは、NP完全（またはそのようなもの）であるため、48項目で完全に答えることができないパーティション化問題の形式です。これを行うための実用的で一般的に認められている近似アルゴリズムを探しています。これは、遺言や財産を解決する際に多くの人が直面する問題です。答えはどこかにあるに違いありません！答えは、コンピュータスクリプトまたは単なる手動の方法である可能性があります。

「一般的に受け入れられている」ヒューリスティックで十分です。プログラマーの帽子をかぶって、ほぼ完璧な解決策を探しています。私の合法的な遺言執行者の帽子をかぶって、「十分に良い」と一般に認められている、または法的な前例があるものを探します。

プログラミング言語環境：LibreOfficeのビジュアルベーシックその他の調査：ウィキペディア、MathIsFun、CodingTheWheel

特定の方法でセットのパーティションを生成したいと思います。これらのパーティションを生成するプロセスで、サイズが N でないすべてのパーティションを除外する必要があります。一般的な解決策は、「セットのすべての「一意の」サブセットを生成する（パワーセットではない）」です。

S次のサブセットを含むセットの場合:

および次の「一意の」要素:

引数で実行された関数/メソッドの結果は次のN = 2ようになります。

次のパーティションは、関数/メソッドによって除外する必要があります。

基礎となるデータ構造は重要ではなく、配列、セットなどの可能性があります。

理由: すべてのパーティションを生成する関数/メソッドはかなり計算量が多いため、すべてのパーティションの完全なセットを取得する前に、いくつかのパーティションを除外する必要があります。

「セットのパーティションの生成」によると、可能なパーティションの数は非常に多くなる可能性があります: 23 要素の場合、44152005855084346 です。私のデータは開始セットで 50 ～ 300 要素なので、どこかに保存する前に、N と等しくないサイズのパーティションを確実に除外する必要があります。

注: この質問は、以前の同様の質問の再考に基づいています。

Erlang のsofs:partitionが、ウィキペディアのSet partitionsに関するページで説明されているのと同じことを行うかどうかを知りたいです。

もしそうなら、どうすれば次の結果を得ることができますか？

与えられたデータ構造 (セットのセットまたはリストのリスト):

次のユニークな要素が含まれています。

引数を指定して関数を実行した結果は次のN = 2ようになります。

次のパーティションは、実行プロセスで除外する必要がありますsofs:partition。

sofs:partition でこれを行うことはできますか? はいの場合、実行中にパーティションを捨てて、繰り返し実行できlength(Partition) =/= Nますか? sofs:partitionN引数を導入するために関数を何らかの方法で再定義することは可能ですか?

名前のリストがあります。

このリストを指定したサイズのグループに分割したいと考えています。すべてのグループは、指定されたサイズ以下である必要があり、グループ全体のグループ サイズはできるだけ等しく、指定されたサイズにできるだけ近くする必要があります。

最も適切なグループ サイズを決定するアルゴリズム (可能であれば Java 風の疑似コードをお願いします!) はどれですか?

例えば：

リストには 13 名が含まれます - 最大チーム サイズ 3。出力 (グループ サイズ): 3、3、3、2、2

リストには 13 人の名前が含まれています - 最大チーム サイズは 4 です。出力: 4、3、3、3

リストには 31 人の名前が含まれています - 最大チーム サイズは 5 です。出力: 5、5、5、4、4、4、4

リストには 31 人の名前が含まれています - 最大チーム サイズは 6 です。出力: 6、5、5、5、5、5

リストには 31 名が含まれます - 最大チーム サイズは 10 です。出力: 8、8、8、7

セットがありSます。Nサブセットが含まれています（さまざまな長さのサブセットが含まれています）。

Lセットに含まれている「一意の」要素のリストもありますS。

各サブセットの各サブセット間で可能なすべての組み合わせを見つける必要があります。これにより、結果の各組み合わせには、リストから1つの要素が含まれますLが、要素の出現回数は任意になります[*]（ワイルドカード要素です）。

したがって、上記のセットで機能する必要な関数の結果は次のようSになります（100％正確ではありません）。

したがって、基本的に、次のことを行うアルゴリズムが必要です。

1. サブセットからサブセットを取得し1、
2. これまでに取得した「一意の」要素のリストを維持するサブセットからもう1つのサブサブセットを追加します2（サブセットに要素が含まれている場合、「一意の」リストのチェックはスキップされ*ます）。
3. 2に達するまで繰り返しNます。

言い換えると、可能なすべての「チェーン」（の場合はペア、の場合N == 2はトリプルN==3）を生成する必要がありますが、各「チェーン」には、生成された各要素で何度も発生する可能性Lのあるワイルドカード要素を除いて、リストから1つの要素が含まれている必要があります。*鎖。

これを行う方法は知っていますがN == 2（単純なペア生成です）、の任意の値を処理するようにアルゴリズムを拡張する方法がわかりませんN。

ここでは、第2種のスターリング数が役立つかもしれませんが、目的の結果を得るためにそれらを適用する方法がわかりません。

注：ここで使用するデータ構造のタイプは、私にとって重要ではありません。

注：この質問は、以前の同様の質問から発展したものです。

通常のパーティションは、インデックス i <= j を持つ各要素が選択されたピボットよりも小さく、インデックス m > j を持つ各要素がピボットよりも大きくなるようなインデックス j を返すため、j がピボットであるという保証はありません。新しいピボット位置を正確に返す別のインプレース パーティション アルゴリズムを作成することは可能でしょうか? 最初はチョイスンピボットを最後に動かそうと思ったのですが、最適解には至りません。

私は数週間、自分自身にPrologを教えようとしてきました。partition/3現在、次のように機能させたい述語を使用して、いくつかの小さな整数から大きな整数を作成するすべての方法を見つけようとしています。

したがって、1、2、および3から4を作成するすべての方法を見つけます。[1、2、1]および[2、1、1]のような重複するソリューションは問題ありませんが、おそらく回避するのは難しいことではありません。これが私が今持っているものです：

Nは最終的にゼロになり、そこに到達した減算は3番目の引数にリストとして配置されるという考え方です。3番目と4番目のルールは正の整数でのみ機能し、2番目のルールは入力が不足しないように指示し、最初のルールはNがゼロに達したときにパーティションが有効であることを通知します。問題は、私が得るのは：

1番目と2番目のルールは私には理にかなっています。3番目と4番目のルールは気難しいように見えますが、特に問題は見つかりません。OTMがゼロになると出力テールがインスタンス化されないかもしれないと思いましたが、最初のルールがそれを処理します。それとも、Prologがどのように機能するかについての根本的な誤解がありますか（これは私にとって頻繁に起こるようです）？

また、N =< 0, fail;部品は冗長ですか？それらは冗長に見えますが、うまくいくものを手に入れるまで確信が持てません。

編集：私はGNUPrologを使用しています。

辞書式順序をM個の偶数サイズのバケット（+/- 1文字列）に分割したいN個の文字列があります。また、N>>M。

直接的な方法は、すべての文字列を並べ替えて、結果のリストをM個のバケットに分割することです。

代わりに、完全なリストが利用可能になる前に、作成された各文字列をバケットにルーティングすることで、これを概算したいと思います。

文字列をバケットに割り当てるための高速でPythonの方法はありますか？私は基本的に、整数モジュロ演算子の文字列に相当するものを探しています。おそらく、辞書式順序を保持するハッシュですか？それも可能ですか？