Okay. I jiggered and poked it (my apologies if you're sensitive to such things), and added a little trace and got this:
#! perl -slw
use strict;
sub show {
my ( $ary, $swaps ) = @_;
printf "%2d swaps => %s\n", $swaps, join ' ', @$ary;
}
sub swapElems {
my $t = $_[0][ $_[1] ]; $_[0][ $_[1] ] = $_[0][ $_[2] ]; $_[0][ $_
+[2] ] = $t;
print "[@{$_[0]}] $_[1] <=> $_[2]"
}
sub do_swaps {
my( $ary, $x, $y, $swaps ) = @_;
print "do_swaps: $x .. $y";
return $swaps if $y == @$ary;
my $saved_y = $y;
for( $x .. $y - 1 ) {
$y = $saved_y if $y == @$ary;
swapElems( $ary, $x++, $y++ );
++$swaps;
}
return do_swaps( $ary, $x, $y, $swaps );
}
sub swap {
my ( $ary, $offset ) = @_;
my $swaps = do_swaps( $ary, 0, $offset, 0 );
show( $ary, $swaps );
}
#swap( [ qw( a b c 1 2 3 ) ], 3 ); # aref, offset of Y0
#swap( [ qw( a b c d 1 2 ) ], 4 );
#swap( [ qw( a b c d e 1 ) ], 5 );
swap( [ qw( a b c d e f g h i j 1 2 3 4 5 6 7 8 ) ], 10 );
#swap( [ qw( a b c d e f 1 2 3 ) ], 6 );
Which when run on the 6/3 testcase produces: do_swaps: 0 .. 6
[1 b c d e f a 2 3] 0 <=> 6
[1 2 c d e f a b 3] 1 <=> 7
[1 2 3 d e f a b c] 2 <=> 8
[1 2 3 a e f d b c] 3 <=> 6
[1 2 3 a b f d e c] 4 <=> 7
[1 2 3 a b c d e f] 5 <=> 8
do_swaps: 6 .. 9
6 swaps => 1 2 3 a b c d e f
6 swaps is a perfect score. and the logic is very clear and very clean. So clean it is beautiful (which always feels right!):
- Switch the 3 from end with the 3 from the front.
- Then switch 3 from the middle with the 3 from the end.
With a 10/7 testcase things are little more muddy: do_swaps: 0 .. 10
[1]b c d e f g h i j[a]2 3 4 5 6 7] 0 <=> 10
[1[2]c d e f g h i j a[b]3 4 5 6 7] 1 <=> 11
[1 2[3]d e f g h i j a b[c]4 5 6 7] 2 <=> 12
[1 2 3[4]e f g h i j a b c[d]5 6 7] 3 <=> 13
[1 2 3 4[5]f g h i j a b c d[e]6 7] 4 <=> 14
[1 2 3 4 5[6]g h i j a b c d e[f]7] 5 <=> 15
[1 2 3 4 5 6[7]h i j a b c d e f[g] 6 <=> 16 *
[1 2 3 4 5 6 7 a[i]j h[b]c d e f g] 7 <=> 10
[1 2 3 4 5 6 7 a b[j]h i[c]d e f g] 8 <=> 11
[1 2 3 4 5 6 7 a b c[h]i j[d]e f g] 9 <=> 12
do_swaps: 10 .. 13
[1 2 3 4 5 6 7 a b c d[i]j h[e]f g] 10 <=> 13
[1 2 3 4 5 6 7 a b c d e[j]h i[f]g] 11 <=> 14
[1 2 3 4 5 6 7 a b c d e f[h]i j[g] 12 <=> 15
do_swaps: 13 .. 16
[1 2 3 4 5 6 7 a b c d e f g[i]j[h] 13 <=> 16
[1 2 3 4 5 6 7 a b c d e f g h[j|i] 14 <=> 16
[1 2 3 4 5 6 7 a b c d e f g h i j] 15 <=> 16
do_swaps: 16 .. 17
16 swaps => 1 2 3 4 5 6 7 a b c d e f g h i j
- Switch the
107 from the end, with the 107 from the front.
- Then switch the 3 so far unmoved with the adjacent 3 that have.
- The wiggle those latter 3 the rest of the way to the end in a series of interleaved swaps, in 2 passes.
I'm not sure what to think about that.
It sure looks like that, after the first 7(*) have been moved, then you could recurse to move the 3 to the end.
Ie. As your algorithm works regardless of long/short ordering, treat it as a 3/7 input.
Of course you'd have to 'lie' about the length of the array, which is easy to do in C, but not so in Perl.
I'm not sure if that is optimal -- I haven't (tried to) figured a formula, but it won't be grossly over -- but it sure looks like (that phrase again), that after a clean start, the end seems (perhaps, unnecessarily) busy?
I'll need to code yours and hdbs algorithms, (and finish my own/graff/bitingduck version, if I can), in C and run them on some big buffers with awkward ratios:
eg. 2GB left buffer and 536870909 & 536870923 (primes either side of 2GB/4) which ought to trigger pathological behaviour if it exists.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
|