問題タブ [combinatorics]

私は自分の仕事でいくつかのグループ化の問題に取り組んでいました。かなりの数の質問があります、ご容赦ください。とても面白いと思います。ここの誰かが組み合わせ論にも興味があるなら、私を助けてください。

さて、たくさんのキャラクターがいます。ここで私はエイズを取りました。

1. 要素をグループ化する方法は何ですか？4文字のエイズがあるとしましょう。有効なグループ（順序を保持）は次のようになります。

   エイズaidsa id s ai ds
   ai dsaids エイズ エイズ
   
   
   
   
   
   

すべてのグループをどのように列挙しますか？n文字の組み合わせはいくつありますか？

2。特殊なケース

• Aisdとaisdが2つのグループであるように、ケースが違いを生んだ場合はどうなりますか？

• すべてのケースを列挙するのにどのくらい時間がかかりますか？4文字と5文字の大文字小文字を見つけることの時間差はどのくらいですか？

• 「空白」をキャラクターにすると。すべての列挙の後、あなたは何文字を書きましたか？

• 距離の観点から単語から別の単語への変換を定義する場合。文字「i」を1ステップ移動する必要があるため、「aids」と「aids」の距離は1であると言います。任意の単語の両側にn距離の単語を見つけることができますか？

編集：
「エイズ」は一言です。
「aids」「aids」は、元の単語「aids」から1つの距離にある2つの単語です。
「aids」は、元の単語「aids」から2距離離れた単語です。
「エイズ」とは、単語から3距離離れた単語のことです。

この問題は金鉱のようです。

ボーナス：2つの単語間の最小距離はどれくらいですか。「エイズ」のように、「エイズ」から1つの距離であり、2つの距離でもあります。列挙内の他の単語に最短距離で到達できる「中間」単語はありますか？単語から別の単語へのパスはいくつありますか？

"ABCDEF" のように、任意のイテラブルを指定します。

それを数値システムのように扱うと、次のようになります。

A B C D E F AA AB AC AD AE AF BA BB BC .... FF AAA AAB ....

このリストでi^番目のメンバーを見つけるにはどうすればよいでしょうか? それらすべてを数え上げるのではなく、効率的に。このリストで 10 億番目 (たとえば) のメンバーを見つけたいと思います。私はpythonでこれをやろうとしていて、私はitertoolsにアクセスできないので関連するかもしれない2.4を使用しています(選択ではありません)。

ナイスですが、必須ではありません。疑似「混合基数」システムのソリューションを一般化できますか?

- - 結果 - -

回:

いくつかの背景: 私は、私が抱えている問題を解決するための多かれ少なかれ力ずくの検索アルゴリズムを書いています。これを行うには、すべての可能性を生成して評価し、最適なものを見つける必要があります。評価には実際には時間がかかるため、検索スペースを完全にカバーするソリューションをできるだけ生成しないようにします。さらに、これを実行できる要素が多ければ多いほど良いです。任意の数 K に対して、通常は K です! 順列、およびそれらすべてを生成することは、~10 を超える数では困難です。

実際の問題: 検索空間には、2 つの要素 (N 回の el1 と M 回の el2、ここで K=M+N) のすべての順列が含まれている必要がありますが、次の制限があります。

1. それらは一意である必要があります (つまり、[aabbb] は 1 回だけ必要です)
2. 順列の逆は必要ありません (つまり、[aab] がある場合、[baa] も必要ありません)。
3. 順列は循環的であると考えているため、[aab] = [aba] = [baa]

これができれば、可能性の数は大幅に減少します。K は理想的には大きいため、最初にすべての順列を生成してから、これらの基準に従ってそれらをフィルター処理することは現実的ではありません。私はすでに最初の制限 (以下を参照) を行っており、Matlab の通常の順列関数 (perms) の 2^K から K!/N!M! に数を減らしました。これは大きな勝利です。2 番目の制限は可能性の数を半分に削減するだけですが (最良の場合)、3 番目の制限も可能性の数を実際に削減できるはずだと思います。

誰かがそれを行う方法を知っていて、できれば可能性の数を計算する方法を知っていれば、それは私を大いに助けてくれるでしょう! 説明を希望しますが、コードも問題ありません (C に似た言語、Java(Script)、Python、Ruby、Lisp/Scheme を読むことができます)。

興味のある方へ: これまでに私が持っている一意の順列のみを取得するアルゴリズムは次のとおりです。

• N-1 と M の順列がすべてある場合は、それらを使用して、e1 を挿入することで N と M の順列を見つけることができます。ただし、重複が発生するため、どこにでも挿入することはできません。なぜこれが機能するのかはわかりませんが、古いものから生成される新しい可能性の数を計算できます (私はこれを「ゲイン」と呼びます)。この数は、最初の古い順列の M+1 から始まり、古い順列ごとに 1 ずつ減少してゼロになり、その時点で M に戻ります (M>=N の場合のみ機能します)。したがって、N=3 と M=3 の順列を計算したい場合、N=2 と M=3 の順列が 10 個ある場合、それらのゲインは [4 3 2 1 3 2 1 2 1 1] になります。

製品コンフィギュレータで可能な組み合わせの数を決定するためのルーチンをプログラムするように依頼されました。

設定は本当に簡単です。これよりも多くの機能がありますが、n個のオプションの1つを選択する必要があるいくつかの「ラジオグループ」（UIコントロールなど）としてモデル化できます。

使用できる制約の種類は、あるオプションが選択されている場合は別のオプションを選択できないというルールだけです。

したがって、私がやりたいのは、一連のオプショングループと制約を前提として、構成できるさまざまな製品の数を計算することです。

私は、包除原理を使用してこれを解決するための素朴なアプローチを行いました。ただし、私が見る限り、このメソッドに基づくアルゴリズムはすべてO（2 ^ n）で実行する必要があり、機能しません。もちろん、適切なランタイムを提供する可能性のある最適化はいくつかありますが、それでも簡単に構築できる最悪のシナリオがあります。

それは私が今いるところです。助言がありますか？

アップデート

ルールがどのように適用されるかを十分に説明していないことに気づきました。

オプション付きのグループがいくつかあります。各グループで選択する必要があるオプションは1つだけです。グループには1つ以上のオプションがあります。

制約のタイプは1つだけです。あるグループのオプションAが選択されている場合、他のグループのオプションBは選択できません。制約はいくつでもかまいません。オプショングループまたはオプション自体に適用される制約/ルールの数に制限はありません。

したがって、例は次のようになります。

グループ1：
x1 x2 x3 x4 x5

グループ2：
y1 y2 y3

グループ3：
z1 z2 z3 z4

制約：
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

*group1でオプションx1が選択されている場合、グループ2のオプションy2は選択できません。

包含-除外を使用して、組み合わせの数を次のように計算します

組み合わせ=C_{ルールなし--Cr} -- C _r [2] _{--C r} [3] + C _r [1,2] + C _r [1,3] + C _r [2,3] --C _r [1、 2,3][1]

どこ

C_{ルールなし}=5* 3 * 4

C _r [a、b、c] =ルールa、b、およびcに違反する組み合わせの数。

残念ながら、この方法には2^|ルール|が必要です。計算。

1 人が 8 面体のサイコロを 20 個振って、合計 8 の 20 乗の可能な結果が得られるゲームを想定します。特定のイベントが発生する確率を計算するには、イベントが発生する可能性のある方法の数を 8^20 で割ります。

値 3 のサイコロを正確に 5 つ得る方法の数を計算できます。(20 が 5 を選択) は、3 のオーダー数を示します。7^15 は、15 回のロールで値 3 を取得できない方法の数を示します。 .

答えは、文字列 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0 を並べ替えることができる方法の数として見ることもできます,0,0 (20 は 5 を選択) にゼロの値の総数 (有効な値が 7 つあると仮定) 7^15 を掛けます (これは正しいです)。

• 質問 1: 同じ値 (つまり、すべてのサイコロの値) のサイコロを正確に 5 つ得る方法の数を計算するにはどうすればよいですか? 注: 上記の最初の答えを単純に使用して bt 8 を掛けると、膨大な量の二重カウントが発生しますか?

  ケース (5 1's)、(5, 2's)、(5, 3's)、... (5's, 8) のそれぞれについて、それらを合計することができることを理解しています (より単純には 8*(5 1's) )。次に、オーバーラップ数の合計 (5 1) と (5 2)、(5 1) と (5 3)... (5 1) と (5, 2) と ... と (5, 8) を引きます。しかし、これは非常に面倒です。これを一般化して、多数のサンプルと多数のクラスにスケールアップします。

• 同じ値のサイコロを 5つ以上得る方法の数を計算するにはどうすればよいですか?

  したがって、11111000000000000000 または 11110100000000000002 または 11111100000001110000 または 11011211222222223333 ですが、00001111222233334444 または 00051174134252 ではありません。

数学を説明するか、これをサポートするライブラリ（特にpythonモジュール）を指す答えを探しています。詳細と例の追加ポイント。

リストのリストを生成 (または印刷、私は気にしません)可能な限り最小限のコード行で、サイズ Nのパスカルの三角形を生成します!

これが私の試みです（トリックを使用してpython 2.6で118文字）：

説明：

• リスト内包表記の最初の要素 (長さが 0 の場合) は[1]
• 次の要素は次の方法で取得されます。
• 前のリストを取得して 2 つのリストを作成します。1 つは先頭に 0 をパディングし、もう 1 つは最後にパディングします。
  • たとえば、2 番目のステップでは、取り[1]、作成[0,1]し、[1,0]
• 2 つの新しいリストを要素ごとに合計する
  • たとえば、新しいリスト[(0,1),(1,0)]を作成し、合計でマップします。
• n回繰り返すだけです。

使用法 (かなりの印刷で、実際には code-golf xD から):

出力：

各単語がランダムな子音で始まり、その後母音と子音が交互になる場合、英語の小文字のアルファベットから長さ 6 の単語をいくつ生成できますか?

アルファベットに数字を追加するとどうなりますか?

この質問も参照してください。

以下を計算する必要がある友人がいます。

完全なグラフ Kn (k<=13) には、k*(k-1)/2 個のエッジがあります。各エッジは 2 つの方法で方向付けられるため、2^[(k*(k-1))/2] の異なるケースになります。

彼女は計算する必要があるP[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X !-> Y は「X から Y への経路がない」ことを意味し、P[ ] は確率です。

したがって、ブルートフォース アルゴリズムは 2^[(k*(k-1))/2] 個の異なるグラフをすべて調べることであり、それらは完全であるため、各グラフで A、B の 1 つのセットを考慮するだけで済みます。 C、D は対称性によるものです。

次に、P[A !-> B] は、「ノード 1 と 2 の間にパスがないグラフの数」をグラフの総数で割った値、つまり 2^[(k*(k-1))/2] として計算されます。

ブルートフォース法は K8 までの Mathematica で機能しますが、彼女には K9、K10... K13 までが必要です。

明らかに、ケースで最短経路を見つける必要はありません。最短経路があるかどうかを見つけたいだけです。

最適化の提案はありますか? (これは典型的な Project Euler の問題のように聞こえます)。

例：

最小グラフ K4 には 4 つの頂点があり、6 つのエッジがあります。したがって、4 つの頂点 A、B、C、および D にラベルを付ける場合、エッジに方向を割り当てる方法は 2^6 = 64 通りあります。

一部のグラフでは、A から B へのパスはありません (それらの X としましょう)。他のグラフでは、C から D へのパスはありません (Y としましょう)。しかし、一部のグラフでは、A から B への経路がなく、同時に C から D への経路もありません。これらは W です。

だからP[A !-> B]=X/64、P[C !-> D]=Y/64そしてP[A !-> B && C !-> D] = W/64。

アップデート：

• A、B、C、D は 4 つの異なる頂点であるため、少なくとも K4 が必要です。
• DIRECTED グラフを扱っていることに注意してください。したがって、UT 行列を使用した通常の表現では十分ではありません。
• Mathematica には、有向グラフのノード間の距離を求める関数があります (無限大を返す場合、パスはありません)。ただし、パスまたはいいえ。

私が次の番号のグループを持っている場合、私は知っています

10を使用して、5040の異なる4桁の数字を使用できます。/（10-4）！

しかし、最初のグループで1つの番号を繰り返すと、次のようになります。

いくつの異なる4桁の数字を作成できますか？私は答えが3360であることを知っています、ただそれを実装する方法がわかりません。

重要：この場合、「1123」や「1213」などの番号は有効な組み合わせである必要がありますが、最初のグループには2つしかないため、「1113」ではありません。

また、グループのために

21904桁の数字が必要です。これらの答えを計算する方法についてのアイデアはありますか？

これは宿題ではありません。特定のハードウェアからこの数値を取得し、組み合わせの数に応じて、いくつかのデータを返します。