問題タブ [combinatorics]

私は並行性を学ぶことに決め、2つの異なるプロセスからの命令がどのように重複する可能性があるかを知りたいと思いました。両方のプロセスのコードは、各反復で3つの命令が実行される10回の反復ループです。問題は、ある時点でX命令を固定したままにして、他のプロセスからの他のX命令を、順序付けする必要があることを考慮してスペースの間に収めることであると考えました（プロセスBの命令4は常に命令20の前に来る必要があります）。

この数を数えるプログラムを作成し、結果を見て、解がnの組み合わせkであることがわかりました。ここで、kは1つのプロセスのループ全体で実行される命令の数であるため、10回の反復では30になります。 nはk*2（2プロセス）です。言い換えると、n / 2が固定され、スペースの間にn / 2を収める必要がある、n個のオブジェクト。後者のn/2は順序を失うことはありません。

問題は解決しました。いいえ、そうではありません。これがなぜであるかはわかりません。組み合わせの定義は、n個のグループからk個の要素を取得して、すべてのグループが異なるが、要素を取得する順序が異なるようにする方法がいくつあるかを理解しています。重要です。この場合、n個の要素があり、すべての命令が実行されるため（n C n）、実際にはそれらすべてを取得しています。

バッグの中に2kの青（A）と赤（B）のオブジェクトがあり、バッグからk個のオブジェクトを取り出すと説明すると、2k個の命令が実際に実行されたときにk個の命令しか取得しません。これに光を当てていただけませんか？

前もって感謝します。

私のコードには、動的な数のリストを含む INPUTS というリストがあります。それらを A、B、C、.. N と呼びましょう。これらのリストには、動的な数のイベントが含まれています。

イベントの組み合わせごとに関数を呼び出したいと思います。例を示します。

組み合わせごとに関数を何度も呼び出す必要があります (入力カウントは動的です。この例では 3 つのパラメーターですが、多かれ少なかれ可能性があります)

これが私がこれまで考えてきたことです。これまでの私のアプローチは、組み合わせのリストを作成することです。要素の組み合わせ自体は、入力配列 A、B、および C への「インデックス」のリストです。例:

マイリスト iCOMBINATIONS には、次の iCOMBO リストが含まれています

次に、これを行います：

しかし、任意の数の INPUTS とそのイベントに対してリスト iCOMBINATIONS を作成する方法を見つける必要があります。何か案は？

実際にこれよりも優れたアルゴリズムはありますか? 私を助ける擬似コードは素晴らしいでしょう。

C# (または VB)

ありがとうございました

私は（HWではなく）自分でプログラミングについて読んでいます。1つの演習では、パスカルの三角形をRでプログラミングしました。最初のアイデアは、リストを作成してから追加することでしたが、うまくいきませんでした。それから、ベクトルから始めて、最後にそれからリストを作成することを考えました。それから、マトリックスを作成し、最後にそれからリストを作成することを考えました。

これにアプローチする方法がわからない。

ヒントはありますか？

ありがとう

これは宿題ではありません。

この記事で Linq ライブラリを称賛し、それが組み合わせ論を行う上でどれほど優れているかを賞賛しているのを見て、「 Python はもっと読みやすい方法でそれを行うことができる」と思いました。

Pythonで30分軽くたたくと、失敗しました。中断したところから終了してください。また、可能な限り最も Pythonic で効率的な方法で実行してください。

ありがとう！

これは非数学者からの組み合わせ論に関する質問なので、我慢してみてください!

n個の異なる文字の配列が与えられた場合、最小変更順序、つまり、世代i + 1に世代iになかった文字が1つだけ含まれる順序で、k個の文字のサブセットを生成したいと考えています。それ自体はさほど難しいことではありません。ただし、ジェネレーション i+1 でスワップアウトされたキャラクターが、ジェネレーション i でスワップインされたキャラクターと同じであるケースの数を最大化したいとも考えています。たとえば、n=7、k=3 の場合:

abc abd abe* abf* abg* afg aeg* adg* acg* acd ace* acf* aef adf* ade bde bdf bef bcf* bce bcd* bcg* bdg beg* bfg* cfg ceg* cdg* cde cdf* cef def deg dfg efg

アスタリスク付きの文字列は、最大化したいケースを示しています。たとえば、第 3 世代で新しい e である abe は、第 2 世代で新しい abd であった ad を置き換えます。これをすべての世代で実現することは不可能に思えますが、可能な限り頻繁に実現したいと考えています。

私が使用する典型的な配列サイズは 20 ～ 30 で、サブセット サイズは 5 ～ 8 前後です。

私は奇妙な言語Icon (または実際にはその派生Unicon ) を使用しているため、私が直接使用できるコードを投稿する人はいないと思います。しかし、疑似コードでの回答やヒントに感謝し、C などの翻訳に最善を尽くします。また、この種の問題は整数の配列の観点から議論されることが多いことに気付きました。解決策を確実に適用できます。私自身の問題にそのような用語で投稿されました。

ありがとう

キム・バスティン

2010 年 6 月 15 日編集:

私は思っていたよりも深い水の中に入ったようです。すべての回答に感謝していますが、すべてが関連しているわけではありません. 適切ではない解決策の例として、最小限の変更順序で文字セット s の k-ary サブセットを生成するための私自身の Unicon 手順を投稿させてください。コードを理解するために知っておく必要があることは次のとおりです。前置された * は構造体のサイズを意味するため、s が文字列の場合、*s は s のサイズ (含まれる文字数) を意味します。|| 文字列連結操作です。前置き！構造体の各要素 (文字列の各文字など) を、連続するパスで順番に生成します。また、「サスペンド」制御構造はプロシージャから結果を返しますが、すべてのローカル変数が配置された状態でプロシージャを「サスペンド」のままにします。

上記の手順の出力は、私の感覚では最適ではないことに注意してください。これまでの調査結果の 1 つは、n 要素の k-ary サブセットのリストの最大「スワッピング スコア」は、comb(n-1, k) より小さくない、または n=7 の場合、k= 3、最大スコアは少なくともcomb(6, 3) = 20です。リストの「スワッピングスコア」を、それ自体が新しい前のアイテムの要素を新しい要素で置き換えるリスト内のアイテムの数として定義します。これを証明するための数学的機器は持っていませんが、k=1 または k=2 で簡単に確認できます。特定の (n,k) では、n=7、k=3 の場合のように、わずかに高いスコアが可能です。

abc abd abe abf
abg acg adg aeg afg
efg dfg cfg bfg
beg bdg bcg
bcd bce bcf
bdf bef
def cef aef
adf acf
acd ace
ade
bde cde
cdf cdg
ceg
deg (交換スコア = 21)

上記のリストは「強力な最小限の変更順序」(ゴルフという言葉のように: 新しいキャラクターは、置き換えられるキャラクターと常に同じ位置にある) であることに注意してください。数日中に何か投稿したいと思っています。

キム

編集: 「シマウマの所有者」をプログラムで解決するを参照してください。同様のクラスの問題に対して

LSAT には、次のような論理問題のカテゴリがあります。

時系列順に I から 7 までの番号が付けられた放送の 7 つの連続したタイムスロットは、G、H、L、O、P、S の 6 つの歌のテープと、ちょうど 1 つのニュース テープで埋められます。各テープは異なるタイム スロットに割り当てられ、どのテープよりも長いテープはありません。ブロードキャストには次の制限が
あります。L は O の直前に再生する必要があります。
ニュース テープは L の少し後に再生する必要
があります。 G は P の後に来ます。

テストの勉強方法として、またプログラミングの課題として、条件を満たす順列のリストを生成することに興味があります。ただし、これがどのクラスの順列問題であるかはわかりません。型の問題を次のように一般化しました。

長さ n の配列 A が与えられた場合:

1. n 個の一意のアイテムのセットを A 内に配置する方法は何通りありますか? 例えば。ABCDEFG を並べ替える方法はいくつありますか?
2. 一意のアイテムのセットの長さが A の長さよりも短い場合、セット内のアイテムが複数回出現する可能性がある場合、セットを A 内に配置できる方法はいくつありますか? 例えば。ABCDEF => AABCDEF; ABBCDEFなど
3. セットの項目が「ブロッキング条件」の対象である場合、一意の項目のセットを A 内に配置できる方法はいくつありますか?

私の考えは、制限をエンコードしてから、Python の itertools のようなものを使用して順列を生成することです。考えや提案は大歓迎です。

それぞれが 0 ～ 10 の値のプロパティを含むアイテムの辞書を取得し、さまざまな要素を追加して、どのアイテムの組み合わせが目的の合計を達成するかを選択するスクリプトを作成しようとしています。同じ「スロット」を共有するアイテムのみを使用して、これを行うスクリプトも必要です。

例えば：

次に、スクリプトは、「item_list」ディクテーションから、「スロット」ごとに 1 つのアイテムを使用して、追加したときに目的の結果が得られる組み合わせを選択する必要があります。

たとえば、必要な結果が 'prop_a': 3、'prop_b': 3、'prop_c': 8、'prop_d': 0 の場合、スクリプトは 'item_2'、'item_6'、および 'item_9' を選択します。機能した他の組み合わせと一緒に。

これを達成する方法はありますか？Python や完全なスクリプトである必要はありませんが、理論的にこれを行う方法についての説明だけで十分です。すべての組み合わせをループしてみましたが、すぐに手に負えなくなり、手に負えなくなったようです。実際のスクリプトでは、それぞれ 8 つのプロパティを持つ 20 の異なる「スロット」を使用して、約 1,000 のアイテムに対してこれを行う必要があります。

助けてくれてありがとう！

特定の文字または数字のセットの組み合わせを生成する問題に対する非再帰的なアプローチが必要でした。

したがって、数 n の部分集合 k が与えられた場合、考えられるすべての組み合わせ n!/k!(nk)! を生成します。

再帰的な方法は、前の 1 つの組み合わせが与えられると、組み合わせを提供します。

非再帰的な方法は、ループ インデックスiの指定された値の組み合わせを生成します。

私はこのコードで問題に取り組みました：

n = 4 および k = 3 でテストして動作しますが、k を 3 より大きい数値に変更すると動作しません。

それは（nk）という事実によるものですか？n = 4 の場合、k = 3 は 1 です。k > 3 の場合は 1 より大きくなりますか?

ありがとう。

反時計回りに0からn-1まで列挙されたn個のセクターがあります。これらのセクター間の境界は無限のブランチです（そのうちのn個）。セクターは複素平面に存在し、nが偶数の場合、セクター0とn / 2は実軸で二等分され、セクターは等間隔に配置されます。

これらのブランチは、ジャンクションと呼ばれる特定のポイントで合流します。各ジャンクションは、セクターのサブセット（少なくとも3つ）に隣接しています。

ジャンクション（たとえば、セクター0と1に隣接するジャンクションから開始する前置順序）とジャンクション間の距離を指定すると、ツリーが一意に記述されます。

さて、そのような表現が与えられた場合、それが実際の軸に対して対称であるかどうかをどのように確認できますか？

たとえば、n = 6の場合、ツリー（0,1,5）（1,2,4,5）（2,3,4）には実線上に3つのジャンクションがあるため、実軸に対して対称になります。（015）と（1245）の間の距離が（1245）から（234）までの距離に等しい場合、これも仮想軸に対して対称です。

ツリー（0,1,5）（1,2,5）（2,4,5）（2,3,4）には4つのジャンクションがあり、これは仮想軸または実軸のいずれに対しても対称ではありませんが、180があります。表現の最初の2つのジャンクションと最後の2つのジャンクションの間の距離が等しい場合、回転対称度。

編集：これが6つの枝、距離1のすべての木です 。http：//www2.math.su.se/~per/files/allTrees.pdf

したがって、説明/表現を前提として、実数、虚数、および180度の回転に対して対称であるかどうかを判断するためのアルゴリズムを見つけたいと思います。最後の例は180度の対称性を持っています。

編集2：これは実際に私の研究のためです。mathoverflowにも質問を投稿しましたが、競技プログラミングでの日々は、これはIOIタスクのようなものだと教えてくれます。数学のコードは素晴らしいでしょうが、Java、Python、または人間が読める他の言語で十分です。

（これらの対称性は、量子力学で優れた特性を持つシュレーディンガー方程式の特殊な種類のポテンシャルに対応します。）

{1,1,1,2,2,3,3,3} などのアイテムのセットと、{{3},{1,2},{1 などの制限セットがあります。 ,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. アイテムの順列を探していますが、最初の要素は 3 でなければならず、2 番目の要素は 1 または 2 でなければなりません。

適合するそのような順列の 1 つ: {3,1,1,1,2,2,3}

一般に、この問題のすべての順列をカウントするアルゴリズムはありますか? このタイプの問題に名前はありますか?

説明のために、特定のタイプの「制限セット」についてこの問題を解決する方法を知っています。アイテムのセット: {1,1,2,2,3}、制限 {{1,2}、{1,2,3}、{1,2,3}、{1,2}、{1,2 }}。これは 2!/(2-1)!/1! に等しいです。* 4!/2!/2!. 最初に 3 つを効果的に並べ替えます。これは最も制限が厳しいためです。次に、余裕のある残りのアイテムを並べ替えます。

また...多項式時間。それは可能ですか？

更新: これについては、以下のリンクで詳しく説明します。上記の問題は「完全一致のカウント」と呼ばれ、上記の各順列制限は、占有者に対するスロットのマトリックス上の {0,1} で表されます。

• https://math.stackexchange.com/questions/519056/does-a-matrix-represent-a-bijection
• https://math.stackexchange.com/questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots