Quickselect and generalized inversions. (II)

[Marko Riedel <mriedel@xxxxxxxxxxxxx>]

Greetings.

Question: what is the pattern in the number of QI inversions? Here are 
the first few values:

2 1 1
3 3 3
4 13 11
5 71 49
6 461 259
7 3447 1593
8 29093 11227


Best regards,

Marko Riedel


----------------------------------------------------------------------

#! /usr/bin/perl -w
#

sub fact {
  my ($n) = @_;

  return 1 if $n==0 or $n==1;

  my ($p) = (1);
  $p *= $n-- while $n>1;

  return $p;
}

sub nextperm {
  my ($index, $n) = @_;
  my (@source) = (0..($n-1));
  my (@res) = ();

  for(my $k=$n; $k>0; $k--){
    my ($pos, $el) = ($index % $k);
    $index = ($index - $pos)/$k;

    $el = splice @source, $pos, 1;
    push @res, $el;
  }

  return \@res;
}

sub isqi {
  my ($perm) = @_;
  my ($count, $min, $max) = (0);
  
  for(my ($k, $j)=(0); $k<$#$perm; $k++){
    ($min, $max) = @$perm[$#$perm, 0];
    for($j=1; $j<=$k; $j++){
      $max = $perm->[$j] if $perm->[$j]>$max;
    }
    for($j=$k+1; $j<$#$perm; $j++){
      $min = $perm->[$j] if $perm->[$j]<$min;
    }

    print STDERR join ' ', @$perm[0..$k];
    print STDERR ' ^ ';
    print STDERR join ' ', @$perm[$k+1..$#$perm];

    print STDERR ($max>$min ? ' *' : '') . "\n";
    $count++ if $max>$min;
  }

  return $count==$#$perm;
}

MAIN: {
  my ($upper) = @ARGV;

  if(not defined $upper or
     $upper < 2){
    print "$0 <upper> where <upper> > 1\n";
    exit -1;
  }

  for(my $n=2; $n<=$upper; $n++){
    my ($count, $f) = (0, fact($n));
    for(my ($index) = (0); $index < $f; $index++){
      my ($perm) = nextperm($index, $n);
      $count++ if isqi($perm);
    }

    print "$n $count " . ($f - $count) . "\n";
  }
}