
This organic chemistry task is essentially to implement a tree enumeration algorithm.



Task

Enumerate, without repetitions and in order of increasing size, all possible paraffin molecules (also known as alkanes).



Paraffins are built up using only carbon atoms, which has four bonds, and hydrogen, which has one bond.   All bonds for each atom must be used, so it is easiest to think of an alkane as linked carbon atoms forming the "backbone" structure, with adding hydrogen atoms linking the remaining unused bonds.

In a paraffin, one is allowed neither double bonds (two bonds between the same pair of atoms), nor cycles of linked carbons.   So all paraffins with   n   carbon atoms share the empirical formula     CnH2n+2

But for all   n ≥ 4   there are several distinct molecules ("isomers") with the same formula but different structures.

The number of isomers rises rather rapidly when   n   increases.

In counting isomers it should be borne in mind that the four bond positions on a given carbon atom can be freely interchanged and bonds rotated (including 3-D "out of the paper" rotations when it's being observed on a flat diagram),   so rotations or re-orientations of parts of the molecule (without breaking bonds) do not give different isomers.   So what seem at first to be different molecules may in fact turn out to be different orientations of the same molecule.



Example

With   n = 3   there is only one way of linking the carbons despite the different orientations the molecule can be drawn;   and with   n = 4   there are two configurations:

   a   straight   chain:     (CH3)(CH2)(CH2)(CH3) 
   a branched chain:       (CH3)(CH(CH3))(CH3)


Due to bond rotations, it doesn't matter which direction the branch points in.

The phenomenon of "stereo-isomerism" (a molecule being different from its mirror image due to the actual 3-D arrangement of bonds) is ignored for the purpose of this task.

The input is the number   n   of carbon atoms of a molecule (for instance 17).

The output is how many different different paraffins there are with   n   carbon atoms (for instance   24,894   if   n = 17).

The sequence of those results is visible in the OEIS entry:  

   oeis:A00602 number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers. 
The sequence is (the index starts from zero, and represents the number of carbon atoms):

1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159, 355, 802, 1858, 4347, 10359,
24894, 60523, 148284, 366319, 910726, 2278658, 5731580, 14490245,
36797588, 93839412, 240215803, 617105614, 1590507121, 4111846763,
10660307791, 27711253769, ...



Extra credit

Show the paraffins in some way. 

A flat 1D representation, with arrays or lists is enough, for instance:

*Main> all_paraffins 1
                        [CCP H H H H]
*Main> all_paraffins 2
                        [BCP (C H H H) (C H H H)]
*Main> all_paraffins 3
                        [CCP H H (C H H H) (C H H H)]
*Main> all_paraffins 4
                        [BCP (C H H (C H H H)) (C H H (C H H H)),
                         CCP H (C H H H) (C H H H) (C H H H)]
*Main> all_paraffins 5
                        [CCP H H (C H H (C H H H)) (C H H (C H H H)),
                         CCP H (C H H H) (C H H H) (C H H (C H H H)),
                         CCP (C H H H) (C H H H) (C H H H) (C H H H)]
*Main> all_paraffins 6
                        [BCP (C H H (C H H (C H H H))) (C H H (C H H (C H H H))),
                         BCP (C H H (C H H (C H H H))) (C H (C H H H) (C H H H)),
                         BCP (C H (C H H H) (C H H H)) (C H (C H H H) (C H H H)),
                         CCP H (C H H H) (C H H (C H H H)) (C H H (C H H H)),
                         CCP (C H H H) (C H H H) (C H H H) (C H H (C H H H))]
Showing a basic 2D ASCII-art representation of the paraffins is better; for instance (molecule names aren't necessary):

       methane          ethane               propane               isobutane
 
          H              H   H              H   H   H              H   H   H
          │              │   │              │   │   │              │   │   │
      H ─ C ─ H      H ─ C ─ C ─ H      H ─ C ─ C ─ C ─ H      H ─ C ─ C ─ C ─ H
          │              │   │              │   │   │              │   │   │
          H              H   H              H   H   H              H   │   H
                                                                       │
                                                                   H ─ C ─ H
                                                                       │
                                                                       H
Links

   A paper that explains the problem and its solution in a functional language:
http://www.cs.wright.edu/~tkprasad/courses/cs776/paraffins-turner.pdf

   A Haskell implementation:
https://github.com/ghc/nofib/blob/master/imaginary/paraffins/Main.hs

   A Scheme implementation:
http://www.ccs.neu.edu/home/will/Twobit/src/paraffins.scm

   A Fortress implementation:         (this site has been closed)
http://java.net/projects/projectfortress/sources/sources/content/ProjectFortress/demos/turnersParaffins0.fss?rev=3005

#include <stdio.h>
 
#define MAX_N 33	/* max number of tree nodes */
#define BRANCH 4	/* max number of edges a single node can have */
 
/* The basic idea: a paraffin molecule can be thought as a simple tree
   with each node being a carbon atom.  Counting molecules is thus the
   problem of counting free (unrooted) trees of given number of nodes.
 
   An unrooted tree needs to be uniquely represented, so we need a way
   to cannonicalize equivalent free trees.  For that, we need to first
   define the cannonical form of rooted trees.  Since rooted trees can
   be constructed by a root node and up to BRANCH rooted subtrees that
   are arranged in some definite order, we can define it thusly:
     * Given the root of a tree, the weight of each of its branches is
       the number of nodes contained in that branch;
     * A cannonical rooted tree would have its direct subtrees ordered
       in descending order by weight;
     * In case multiple subtrees are the same weight, they are ordered
       by some unstated, but definite, order (this code doesn't really
       care what the ordering is; it only counts the number of choices
       in such a case, not enumerating individual trees.)
 
   A rooted tree of N nodes can then be constructed by adding smaller,
   cannonical rooted trees to a root node, such that:
     * Each subtree has fewer than BRANCH branches (since it must have
       an empty slot for an edge to connect to the new root);
     * Weight of those subtrees added later are no higher than earlier
       ones;
     * Their weight total N-1.
   A rooted tree so constructed would be itself cannonical.
 
   For an unrooted tree, we can define the radius of any of its nodes:
   it's the maximum weight of any of the subtrees if this node is used
   as the root.  A node is the center of a tree if it has the smallest
   radius among all the nodes.  A tree can have either one or two such
   centers; if two, they must be adjacent (cf. Knuth, tAoCP 2.3.4.4).
 
   An important fact is that, a node in a tree is its sole center, IFF
   its radius times 2 is no greater than the sum of the weights of all
   branches (ibid).  While we are making rooted trees, we can add such
   trees encountered to the count of cannonical unrooted trees.
 
   A bi-centered unrooted tree with N nodes can be made by joining two
   trees, each with N/2 nodes and fewer than BRANCH subtrees, at root.
   The pair must be ordered in aforementioned implicit way so that the
   product is cannonical. */
 
typedef unsigned long long xint;
#define FMT "llu"
 
xint rooted[MAX_N] = {1, 1, 0};
xint unrooted[MAX_N] = {1, 1, 0};
 
/* choose k out of m possible values; chosen values may repeat, but the
   ordering of them does not matter.  It's binomial(m + k - 1, k) */
xint choose(xint m, xint k)
{
	xint i, r;
 
	if (k == 1) return m;
	for (r = m, i = 1; i < k; i++)
		r = r * (m + i) / (i + 1);
	return r;
}
 
/* constructing rooted trees of BR branches at root, with at most
   N radius, and SUM nodes in the partial tree already built. It's
   recursive, and CNT and L carry down the number of combinations
   and the tree radius already encountered. */
void tree(xint br, xint n, xint cnt, xint sum, xint l)
{
	xint b, c, m, s;
 
	for (b = br + 1; b <= BRANCH; b++) {
		s = sum + (b - br) * n;
		if (s >= MAX_N) return;
 
		/* First B of BR branches are all of weight n; the
		   rest are at most of weight N-1 */
		c = choose(rooted[n], b - br) * cnt;
 
		/* This partial tree is singly centered as is */
		if (l * 2 < s) unrooted[s] += c;
 
		/* Trees saturate at root can't be used as building
		   blocks for larger trees, so forget them */
		if (b == BRANCH) return;
		rooted[s] += c;
 
		/* Build the rest of the branches */
		for (m = n; --m; ) tree(b, m, c, s, l);
	}
}
 
void bicenter(int s)
{
	if (s & 1) return;
 
	/* Pick two of the half-size building blocks, allowing
	   repetition. */
	unrooted[s] += rooted[s/2] * (rooted[s/2] + 1) / 2;
}
 
int main()
{
	xint n;
	for (n = 1; n < MAX_N; n++) {
		tree(0, n, 1, 1, n);
		bicenter(n);
		printf("%"FMT": %"FMT"\n", n, unrooted[n]);
	}
 
	return 0;
}