ANALYSIS of ALGORITHMS, Bulletin Board

# Quickselect and generalized inversions. (II)

```
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";
}
}
```

Date Prev | Date Next | Date Index | Thread Index