Problem Statement

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

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.

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:

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:   The sequence is (the index starts from zero, and represents the number of carbon atoms):

Show the paraffins in some way. A flat 1D representation, with arrays or lists is enough, for instance: Showing a basic 2D ASCII-art representation of the paraffins is better; for instance (molecule names aren't necessary): http://www.cs.wright.edu/~tkprasad/courses/cs776/paraffins-turner.pdf https://github.com/ghc/nofib/blob/master/imaginary/paraffins/Main.hs http://www.ccs.neu.edu/home/will/Twobit/src/paraffins.scm http://java.net/projects/projectfortress/sources/sources/content/ProjectFortress/demos/turnersParaffins0.fss?rev=3005

Let's start with the solution:

use Math::GMPz;

my $nmax = 250;
my $nbranches = 4;

my @rooted   = map { Math::GMPz->new($_) } 1,1,(0) x $nmax;
my @unrooted = map { Math::GMPz->new($_) } 1,1,(0) x $nmax;
my @c        = map { Math::GMPz->new(0) } 0 .. $nbranches-1;

sub tree {
  my($br, $n, $l, $sum, $cnt) = @_;
  for my $b ($br+1 .. $nbranches) {
    $sum += $n;
    return if $sum > $nmax || ($l*2 >= $sum && $b >= $nbranches);
    if ($b == $br+1) {
      $c[$br] = $rooted[$n] * $cnt;
    } else {
      $c[$br] *= $rooted[$n] + $b - $br - 1;
      $c[$br] /= $b - $br;
    }
    $unrooted[$sum] += $c[$br] if $l*2 < $sum;
    return if $b >= $nbranches;
    $rooted[$sum] += $c[$br];
    for my $m (reverse 1 .. $n-1) {
      next if $sum+$m > $nmax;
      tree($b, $m, $l, $sum, $c[$br]);
    }
  }
}

sub bicenter {
  my $s = shift;
  $unrooted[$s] += $rooted[$s/2] * ($rooted[$s/2]+1) / 2  unless $s & 1;
}

for my $n (1 .. $nmax) {
  tree(0, $n, $n, 1, Math::GMPz->new(1));
  bicenter($n);
  print "$n: $unrooted[$n]\n";
}