algorithm - 程序列出碳水化合物链的排列

Question

我的任务是创建一个程序，获取碳氢分子，例如Pentene，c5h10，并输出，最好是图形化的，其分子链的所有可能排列。我并不是要求为我写这本书（事实上，请不要），但有人能给我一个好的起点吗至于语言，我可以使用c、java或javascript和html（我更喜欢使用后者，因为它使图形化的部分更容易）。
规则如下：
每个碳原子必须形成4个键，每个氢原子必须形成一个键。
所有的链都必须有相同数量的碳原子和氢原子（所以它们都是相同的分子）。
两条链被认为是“不同的”，当一条链不能改变成另一条链而不产生或破坏任何键。例如，allthesechains是不同的。
双键存在，并算作2个债券（这听起来像常识，但我包括它来消除任何误解的机会）。
单键可以“扭曲”，即单键另一侧的链条可以翻转然而，双重债券不能。所以，两个单键“扭曲”的链是一样的，但两个双键“扭曲”的链不是一样的。
如果上面有什么不清楚的地方，请问我。
编辑：根据我目前的计算，如果没有碳原子的“环”和双键（双键本质上是只有两个原子的“环”），化合物的公式是CnH2n+2如果公式是cnh2n，和戊烯一样，那么必须有一个且只有一个双键或一个环（如前所述，两者相同）。
编辑2：根据最后一条规则，以下两条链相同：

      H               C-H

     /               /…-C-C       and …-C-C

     \               \      C-H             H

Since the single bond on the left can be twisted.

EDIT 3: In response to David, here is an example of 2 chains that aren't identical:

H H H
 \|/
H C H
 \|/
H C H
 \|/
H C H
 \|/
  C     H
  |    /
  C-C=C
  | |  \
  H H   C-H
        |\
        H H

和

H H H
 \|/
H C H
 \|/
H C H
 \|/
H C H   H H
 \|/    |/
  C     C-H
  |    /
  C-C=C
  | |  \
  H H   H

这是因为要使它们相同，C=C键必须扭曲，这是不允许的，因为它是双键。

Answer 1

无环情况下的算法要简单得多，所以我将从这里开始我建议的计划如下。
根链是一个h（根）与其他h（根）不同的链。生成所有不相等的根链。
对于每个生成的根链，只有在根被“规范地”选择时才保留它（稍后将详细介绍）现在我们有了不相等的链。（在算法文献中，步骤1和步骤2被称为“枚举非同构的无向树”。
拉上铁链。作为第一个切入点，使用Graphviz，但是有很多很多算法“很好地”将树嵌入到欧几里德平面中。这是一个单独的问题。
步骤1
不是生成完整的链，而是生成带有一个开放键的不完整链我们通过结合根h来恢复完整的链。
不完整链是具有三个结合不完整链的h或c。这个定义是递归的，自然生成策略也是如此。生成一个包含n个Cs的不完整链，如下所示。
如果n==0，则输出h。
否则，对于每个三元组n1，n2，n3>=0，使得n1+n2+n3==n，对于每个带有n1 cs的不完整链c1，对于每个带有n2 cs的不完整链c2，对于每个带有n3 cs的不完整链c3，如果c1<=c2<=c3（稍后将详细介绍），则输出由与c1，c2，c3结合的c组成的不完整链。
条件c1<=c2<=c3是因为键的顺序在这里似乎无关紧要（如果我错了，请纠正我），我们不想产生多个置换不过，我还没说c<=c'是什么意思，所以我们来解决这个问题。
如果c==h，则c<=c'。否则，如果C'！=H，则让c1<=c2<=c3为与C的开口C结合的不完整链，让c1'<=c2'<=c3'为与C的开口C结合的不完整链我在完成定义之前使用<=但这没关系，因为这个定义在结构上是归纳的（即递归的）如果C1<=C1'和（（不是C1’<=C1）或（C2<=C2'和（（不是C2’<=C2）或C3<=C3'）），则C<=C'，否则不。换句话说，我们比较（C1，C2，C3）词典学到（C1′，C2′，C3′）。Haskellers，这就是派生的Eq/Ord实例的作用

data IncompleteChain = H | C IncompleteChain IncompleteChain IncompleteChain .

步骤2
我们将再次使用订单。对于每个不完整链c，通过用根h完成c，然后移除不同的h并重组不完整链来生成所有c'（记住，在比较之前要确保结合的不完整链的排序顺序）。如果c小于或等于所有这些c’，则保留c，否则不保留。
一个双键
我要离开这里做热身。让其中一个双键碳具有不完整的单键链c1和c2。让另一个有不完整的单键链c3和c4。如果我理解正确，那么有四种方法来生成等价链（其中一种方法是保持现有链）：可选地与（C3，C4）交换（C1，C2），然后可选地与（C2，C4）交换（C1，C3）。要生成具有双键的所有N-碳链，请考虑所有n1、n2、n3、n4>=0，使n1+n2+n3+n4==n，然后分别考虑具有n1、n2、n3、n4碳的所有不完整链C1、C2、C3、C4。如果c1<=c2和（c1，c2）<=（最小值（c3，c4），最大值（c3，c4），则输出链。
一个环
我们可以用一个环生成所有的n-碳链，如下所示。迭代环中有多少个碳（介于2和n之间的数字k）。遍历分区n1，n1'，n2，n2'，…，nk，nk'>=0，这样n1+n1'+n2+n2'+…+n k+nk'=n-k。用n1，n1，n2，n2'，…，nk，nk'碳在所有不完整链c1，c1，c2，c2'，…，ck，ck'上迭代。链条ci和ci'将与环中的第i个碳连接为了确定给定的c1，c1'，c2，c2'，…，ck，ck'是否应该保留，生成同构表示，如下所示。从列表[c1，c1'，c2，c2'，…，ck，ck']开始。创建第二个列表[ck，ck'，…，c2，c2'，c1，c1']。创建第三个列表[C1'，C1，C2'，C2，…，CK'，CK]和第四个列表[CK'，CK，…，C2'，C2，C1'，C1]。通过在一个循环（例如，[c2，c2'，c3，c3'，…，c1，c1']）中排列碳来创建4个（k-1）更多的列表如果原始列表是所有这些列表的字典最小值，那么保留它。