問題タブ [combinatorics]

n 個の値を持つ配列を作成する関数の下にあります (未回答の前の質問から)。配列の合計は $max に等しくなります。

例: $n = 4 および $max = 30 に設定すると、次のようになります。

ただし、この関数は重複と 0 を考慮しません。私が望んでいて、達成しようとしているのは、事前定義された変数$maxに加算される一意の番号を持つ配列を生成することです。重複した数字と0 および/または負の整数はありません。

組み合わせ問題を解決するアルゴリズムを c# で探しています。

私はオブジェクト1,2,3,4を持っていると仮定します

これらのオブジェクトを、毎回すべてのオブジェクトを含む複数のグループにグループ化するすべての可能な方法を取得したいと考えています。順序は重要ではありません。例：

<1,2,3,4> <1,2 / 3,4> <1,3 / 2,4> <1,4 / 3,2> <1,2,3 / 4> <1,2, 4 / 3> <1,3,4 / 2> <2,3,4 / 1> <1,2 / 3 / 4 > <1,3 / 2 / 4> <1,4 / 3 / 2> < 2,3 / 1 / 4> <4,3 / 1 / 2> <1 / 2 / 3 / 4>

最初のケースでは、4 つのオブジェクトすべてを含む 1 つのグループがあります。次は、さまざまな方法ですべてのオブジェクトを含む 2 つのグループのケースです。最後のケースは 4 つのグループで、各グループには 1 つのオブジェクトのみが含まれます。

Roger Pressman の本には、2 つの入れ子になったループを持つプログラムの例が記述されており、内側のループは 4 つの if ステートメントを囲んでいます。2 つのループは最大 20 回実行できます。彼は、これにより約 10^14 のパスが作成されると述べています。これほど大きな数値を得るには、ループ内のパスに 2^40 を掛けます。つまり、2 つのループを通過する可能性を考慮して、2^20 かける 2^20 です。なぜこの因数が 400 でないのか、つまり 20 かける 20 ではないのかわかりません。pptスライドとプログラムグラフが見れると助かります。ありがとう。

軌跡に沿った点で構成され、各点に関連付けられた座標を持つ一連の軌跡があります。これらを 3D 配列 (trajectory、point、param) に保存します。これらの軌道の可能なペアごとの組み合わせ間の累積距離が最大になる r 個の軌道のセットを見つけたいと思います。私の最初の試みは、次のようになります。

num_traj は約 500 ～ 1000、r は約 5 ～ 20 になる可能性があるため、これには永遠に時間がかかります。k は任意ですが、通常は最大 50 です。

超賢くしようとして、私は itertools を多用して、すべてを 2 つのネストされたリスト内包表記に入れました。

まったく判読できない (!!!) だけでなく、時間がかかります。誰かがこれを改善する方法を提案できますか?

私はこの問題の解決策を探すのにかなり長い時間を費やしました。たくさんのハッチングされた三角形を描き、単純なケースで三角形を数え、ある種のパターンを探しました。残念ながら、私は壁にぶつかりました。私のプログラミング/数学のスキルは、この問題の前提条件を満たしていなかったと確信しています。

そこで、フォーラムにアクセスするための解決策をオンラインで見つけました。私はほとんどの方法をまったく理解していませんでした、そしていくつかはただ複雑すぎるように見えました。

誰かが私にこの問題の理解を与えることができますか？ここにある方法の1つ：http：//www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles（問題C）では、単一の関数を使用できました。

彼らはどのようにしてその解決策を思いついたのですか？この時点で、この興味深い問題の背後にある概念のいくつかを本当に理解したいと思います。解決策を探すことがオイラー精神の一部ではなかったことは知っていますが、とにかくこの問題を解決できなかったと確信しています。

リストがあり、それを別のリストにグループ化しています。

から：

の中へ

このリストから可能なすべての組み合わせを連結して、次のような出力を得るにはどうすればよいですか。

私はset<string>「一」「二」「三」から持っています。

そこからすべてのペアを取得するにはどうすればよいですか?

• 1 - 2
• 1 - 3
• 2 - 3

あるプレイヤー X がプレイヤー Y にボールをパスしたいゲームがありますが、彼は複数のプレイヤーとプレイでき、他のプレイヤーは Y にボールをパスできます。

ボールが X から Y に移動できるパスは何通りあるか知りたいです。

たとえば、彼が 3 人のプレーヤーでプレーしている場合は 5 つの異なるパスがあり、4 人のプレーヤーでプレーしている場合は 16 のパスがあり、20 人のプレーヤーでプレーしている場合は 330665665962404000 のパスがあり、40 人のプレーヤーで 55447192200369381342665835466328897344361743780 のパスがあります。数最大。一緒に遊べる選手は500人。

カタロニア数字を使用することを考えていましたか? これを解決するための正しいアプローチだと思いますか？ヒントを教えてください。

たとえば、他のリストといくつかのゼロで構成されるリストがあります。

内側のリストの順序を変えずに、このリストのすべての組み合わせを生成したいので、

大丈夫ですが、

そうではありません。これは Python ではかなり簡単なはずですが、そうは思いません。誰か助けてくれませんか？

交差する要素が 2 つ以上ない特別なタイプの組み合わせを作成したいと考えています。例を挙げて説明しましょう：

A、B、C、D、E、F、G、H、および I を含む 9 つの文字セットがあるとします。

繰り返しのない標準的な 3 文字の組み合わせを作成すると、9C3 セットになります。これらには、ABC、ABD、BCD などのセットが含まれます。一般的な文字が 1 つだけのセットを作成したいと考えています。したがって、この例では、次のセットを取得します。

ABC、ADG、AEI、AFH、BEH、BFG、BDI、CFI、CDH、CEG、DEF、および GHI - 2 つのセットを使用する場合、繰り返し文字は 1 つしかないことに注意してください。

そのようなセットを生成する良い方法は何でしょうか? サブセットサイズ4で、1000文字のセットに対して実行できるように、スケーラブルなソリューションである必要があります。

どんな助けでも大歓迎です。

ありがとう