java - 计算所有可能的组合

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

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

请注意，对于 n 个音符，如果第一个音符连接到第二个音符，则可能的连接数 ( C(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 自己 你必须在实际函数 C(n) 之外有一个 if 语句来返回 1 而不是 2。否则它会搞砸整个循环.有点乱，但这就是算法中真实世界数据的本质

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

数据表示

我会有一个包含 n 个 boolean 的列表。数组可以正常工作。如果连接了 2 个音符，则数组中的该条目应为 true。我希望索引 0 是第一个和第二个音符的连接，索引 n-1 是最后一个音符是否连接到任何东西。

排列生成

我们计算可能性总数的方式非常适合生成方法 (G(n))。对于 n，我们需要将 E-E 添加到 G(n-2) 并将 E 添加到 G(n-1).

在这种循环的基础上，我们有:

G(0) = {E, E-} 
G(1) = {E-E, E E, E E-}