6

序文

無関係な値 (E としましょう) の 12 要素のリスト、配列、または文字列を考えてみましょう。各要素は、最大で 1 つの他の隣接する要素にリンクできます。または、それがリストの最後の要素である場合は、最初の要素にリンクできます。

有効なリストの例。ダッシュはリンクを示し、「E」は要素を表します。

E E E E E E E E E E E E 
E E-E E-E E E E-E E-E E
E E E-E E E-E E-E E E E-

無効なリストの例。

E-E-E E E E E-E E E E E-

質問

一意のリストの総数を計算して印刷したい。

この問題に取り組むには、データを表現する最善の方法は何でしょうか?

この問題に固有のデータ構造を実装するのが最善でしょうか?

これを Java で実装することを検討していますが、別の言語の方が適していると思われる場合は、提案をお待ちしています。

どうして

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

アイデアは、8 分音符のシングル グループとダブル グループのみで構成される 12/8 のバーですべてのリズミカルなパターンを見つけることです。

4

3 に答える 3

4

ここで可能性の数を計算すると、実際には信じられないほどきちんとした解決策が得られます (私の意見では)。

n 個の音符のC(n)場合、最初の音符が 2 番目の音符に接続されている場合、可能な接続数 ( )は であることに注意してくださいC(n-2)。それ以外の場合はですC(n-1)。この意味は

C(n) = C(n-1) + C(n-2)
C(1) = 3 //Either the first and second are connected, 
         //neither are connected, or the end is connected.
C(0) = 2 //Either the end is connected or it isn't

注:単一の音符の例で、最後の音符が「それ自体に」接続できる場合、G(0) は 1 それ以外の場合は 0 です。さらにE-E、 とE E-が分離しているかC(1)どうかは不明です。 3. これらは 0 または 1 のシーケンスにのみ適用されることに注意してください。2 ではなく 1 を返すには、実際の関数の外側に if ステートメントが必要C(n)です。そうしないと、繰り返し全体が台無しになります。少し面倒ですが、それがアルゴリズムにおける現実世界のデータの性質です

これは、基本的にフィボナッチ数列のバリアントを取得したことを意味します! かっこいいでしょ？

データ表現

nbooleanのリストがあります。配列は正常に機能します。2 つのノートが接続されている場合、配列内のそのエントリは になりますtrue。インデックス 0 は最初と 2 番目のノートの接続であり、インデックスn-1は最後のノートが何かに接続されているかどうかです。

順列生成

可能性の総数を計算する方法は、生成方法 ( G(n)) に適しています。n については、E-EtoG(n-2)とEtoを追加する必要がありG(n-1)ます。

この繰り返しのベースには、次のものがあります。

G(0) = {E, E-} 
G(1) = {E-E, E E, E E-}
于 2012-11-02T04:31:16.800 に答える
0

要素間のスペースをメイン データにすると、12 個の「スペース」ができます (最後のスペースは、最初のスペースに結び付いた最後のスペースです)。

各「スペース」は空白にすることも、リンクを含めることもできます。したがって、0 または 1 として表すことができます。したがって、最大で 2^12 の可能性があります。これはかなり小さい数 (4096) であるため、それらをすべて生成してから、隣接する 1 を持つものを取り除くことができます。

于 2012-11-02T04:33:04.190 に答える
0

バリアントの総数は 466 だと思います。

次のように数を計算できます。

EE リンクが Y としてマークされていると仮定すると、たとえば、12 のうち 2 つの E のみがリンクされている配置 s の総数は、最初のアイテムが 1 であると見なされたときに、2 つのアイテムの繰り返しを含む配置の数に等しくなります。 10回繰り返され、2番目は1回だけ繰り返されると見なされます。基本的に、これは次のリストになります。

Y E E E E E E E E E E 
E Y E E E E E E E E E
E E Y E E E E E E E E
..
E E E E E E E E E E Y

これは基本的に、11 である multinomial(10, 1) を計算するのと同じです ( http://www.wolframalpha.com/input/?i=multinomial%2810%2C+1%29 ) 。

合計数は次の合計です。

multinomial(12) + // there is no E-E link at all 
multinomial(12 - 2, 1) + // only one E-E link 
multinomial(12 - 4, 2) + // two E-E links
...
multinomial(12 - 12, 6)  // 6 E-E links

これは 233 です ( http://www.wolframalpha.com/input/?i=multinomial%2812%29+%2B+multinomial%2810%2C+1%29+%2B+multinomial%288%2C+2%29 +%2B+多項%286%2C+3%29+%2B+多項%284%2C+4%29+%2B+多項%282%2C+5%29+%2B+多項%286%29 )

通常、エンドリンクの可能性を考慮してこれを 2 倍しますが、実際には 3 つの EEE のチェーンが作成され、問題が発生する場合があります。

反対側には、いくつかのパラメーターのすべての多項式の組み合わせを生成するための利用可能なアルゴリズムがあり、それらはすべて 200 のようなものであるため、すべてを生成して、最後に循環リンクで拡張できるものを確認するだけです。

于 2012-11-02T04:33:20.710 に答える