n 碳脂肪族烷烃是由 n 个节点组成的无根树,其中每个节点的度数最多为 4。例如,请参阅此以获取一些低 n 值的枚举列表。
我正在寻找一种算法来计算这种 n 碳脂肪族烷烃的数量,给定 n。
我已经在化学堆栈交换中看到了这一点。我还考虑过动态规划,即从较小的组件构建更大的图,但我无法处理过多计算相同异构体的问题。
澄清:碳只是一个比喻。我不希望考虑 C16 和 C17 的不稳定性,也不关心立体异构体
因此,标准方法是使用Redfield-Pólya 定理,也称为 Pólya 枚举定理。但是它不是很“算法”——你有这样的代码( Mathematica、Haskell 或 Python 版本之一)。
Rosettacode 页面还描述了一种更直接的方法,使用规范检查来避免重复。该算法是有序生成的一种特殊形式(我认为),仅适用于没有边缘颜色顶点且最大价数为 4 的树。