Closures; random BSTs.

["Marko R. Riedel" <mriedel@neuearbeit.de>]

Greetings.

I would have posted more data if I knew how to compute them! The
algorithms involved all have exponential or worse time and space
complexity. I remedied the latter by writing a function called
"walkperms" that iterates over all n!  permutations of n elements and
never allocates more than one permutation, assuming that the Perl GC
is doing its job properly.

I got the following data for the expected closure size when k=1 (two
extra polynomials).

1
z
1/1 1

2
z + z^2
3/2 1.5

3
z + 3 z^2 + 2 z^3
13/6 2.16666666666667

4
z + 9 z^2 + 8 z^3 + 6 z^4
67/24 2.79166666666667

5
z + 25 z^2 + 20 z^3 + 30 z^4 + 24 z^5 + 20 z^6
471/120 3.925

6
z + 75 z^2 + 80 z^3 + 180 z^4 + 144 z^5 + 240 z^6
3271/720 4.54305555555556

7
z + 231 z^2 + 350 z^3 + 840 z^4 + 504 z^5 + 1470 z^6 + 720 z^7 + 504 z^10 + 420 z^12
31333/5040 6.21686507936508

8
z + 763 z^2 + 1232 z^3 + 5460 z^4 + 1344 z^5 + 10640 z^6 + 5760 z^7 + 5040 z^8 + 4032 z^10 + 3360 z^12 + 2688 z^15
299223/40320 7.42120535714286

9
z + 2619 z^2 + 5768 z^3 + 30996 z^4 + 3024 z^5 + 83160 z^6 + 25920 z^7 + 45360 z^8 + 40320 z^9 + 27216 z^10 + 30240 z^12 + 25920 z^14 + 24192 z^15 + 18144 z^20
3291487/362880 9.07045579805997

I got one extra polynomial for the expected size of the automorphism
group of a random BST.

1
z
1/1 1

2
2 z
2/2 1

3
4 z + 2 z^2
8/6 1.33333333333333

4
20 z + 4 z^2
28/24 1.16666666666667

5
72 z + 48 z^2
168/120 1.4

6
504 z + 216 z^2
936/720 1.3

7
3072 z + 1888 z^2 + 80 z^8
7488/5040 1.48571428571429

8
24848 z + 14752 z^2 + 560 z^4 + 160 z^8
57872/40320 1.43531746031746

9
200992 z + 147296 z^2 + 11872 z^4 + 2720 z^8
564832/362880 1.55652557319224



Regards,

Marko Riedel

BTW, I don't have a Ph.D.

#! /usr/bin/perl -w
#

sub vect2perm {
  my ($vect) = @_;
  my (@source, @perm) = (1 .. scalar @$vect);

  for my $i (0 .. $#$vect){
    push @perm, $source[$vect->[$i]];
    splice @source, $vect->[$i], 1;
  }

  return \@perm;
}

sub walkperms {
  my ($n, $proc, @args) = @_;
  my (@vect) = (0) x $n;

  my ($pos);
  do {
    &$proc(vect2perm(\@vect), @args);

    for($pos = $n - 1; $pos >=0; $pos--){
      if($vect[$pos] < $n - 1 -$pos){
	$vect[$pos]++;
	last;
      }
      else{
	$vect[$pos] = 0;
      }
    }
  } while($pos > -1);

  return 1;
}

sub printit {
  my ($perm, $ptr) = @_;

  print "[@$perm]\n"; $$ptr++;
  
  return;
}

MAIN: {
  my ($total);

  for my $n (1..5){
    $total = 0;
    walkperms($n, \&printit, \$total);
    print "$total\n";
  }
}