计算所有可能的组合

Question

前言

考虑一个由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的条形图中找到每个节奏模式,仅由八分音符的单组和双组组成,其中可以绑在条形线上.

Answer 1

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

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。否则它会搞砸整个递归。有点混乱，但这就是算法中现实世界数据的本质

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

数据表示

我会有一个 n 的列表boolean。数组可以很好地工作。如果连接了 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-}