6

前言

考虑一个包含 12 个元素的列表、数组或字符串，它们的值不相关（比如说 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 E-

问题

我想计算唯一列表的总数，并打印它们。

要解决这个问题，表示数据的最佳方式可能是什么？

最好实现一个专门针对这个问题的数据结构？

我希望在 Java 中实现这一点，但如果您认为另一种语言更适合，我愿意接受建议。

为什么

这不是一个家庭作业问题。

这个想法是在一个 12/8 的小节中找到每个节奏模式，该小节仅由八分音符的单组和双组组成，其中八分音符可以绑在一个小节线上。

4

3 回答 3

4

在这里计算可能性的数量实际上有一个非常巧妙的解决方案（在我看来）。

C(n)请注意，对于 n 个音符，如果第一个音符连接到第二个音符，则可能的连接数 ( ) 是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)则为 2 3. 请注意，这些仅适用于 0 或 1 的序列，您必须在实际函数之外有一个 if 语句C(n)才能返回 1 而不是 2。否则它会破坏整个循环。有点乱，但这是算法中真实世界数据的本质

这意味着您基本上已经有了斐波那契数列的变体！酷吧？

数据表示

我会有一个 nboolean的列表。数组可以正常工作。如果连接了 2 个音符，则数组中的该条目应为true. 我会让索引 0 是第一个和第二个音符的连接，索引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，那么例如，当第一个被认为是重复10次，第二次被视为只重复一次。基本上这相当于以下列表：

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

这与计算多项式 (10, 1) 基本相同，即 11 ( 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 以说明最终链接的可能性，但这实际上可以在某些情况下创建三个 EEE 链，这会破坏您的问题。

另一方面，有可用的算法可以为某些参数生成所有多项式组合，并且由于所有参数都像 200 一样，因此很容易生成所有参数，只需检查哪些可以通过循环链接进行扩展。

于 2012-11-02T04:33:20.710 回答