Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: sort with fewest moves (Bose-Nelson algorithm)

by grinder (Bishop)
on Feb 11, 2002 at 10:42 UTC ( #144611=note: print w/replies, xml ) Need Help??


in reply to sort with fewest moves

Algorithms that do this that have been known about since the 1960s. The most well-known one is the Bose-Nelson sort (although trudging through web pages, I seem to be coming across Batcher's Odd-Even Merge Sort more often).

Interestingly enough, there seems to be scant details available on the net. Google doesn't turn up much. I read about this technique in a long-lost issue of Computer Language.

The only link halfway useful that I have found is www.cs.brandeis.edu/~hugues/sorting_networks.html ... I think you're going to have to dig out a copy of Knuth volume III - Searching and Sorting. <update> Hmm, I just did. The Knuth, as usual, is heavy on mathematics and short on algorithms. I still can't find any code to help you. It's in section 5.3.1 (Minimum-comparison sorting) for what it's worth.</update>

The algorithm essentially accepts a single number (the number of elements to sort), and then spits out a series of pairs, which are the indices of the elements to compare. And it turns out that as some of the comparison (a,b) and (c,d) don't affect each other, you can run them in parallel, thereby reducing the overall time taken.

It is apparently very hard to generate a minimal number of comparisons. These days people are attacking the problem through Genetic Algorithm (GA) techniques.


Some more links. Using sorting networks reveals more hits.


print@_{sort keys %_},$/if%_=split//,'= & *a?b:e\f/h^h!j+n,o@o;r$s-t%t#u'

Replies are listed 'Best First'.
Re: Re: sort with fewest moves (Bose-Nelson algorithm)
by hossman (Prior) on Feb 12, 2002 at 06:58 UTC
    I don't think sorting networks will work here.

    If I remember correctly, (and I'm not certain I ever really understood them) they're built on the principle of swaps, and while you can definitely think of a move as a swap where one of the items is empty, a sorting network would suggest solutions that aren't possible.

    For example a if the input was (0,2,1) the solution you would get is swap(1,2) -- but that's not possible. in this case only swaps in which one parameter is currently "0" are valid.

    It really sounds like a Game Playing problem ... here's a recursive solution that tries all the "smart" moves and figures out which one leads to the correct order in the minimal number of moves.

    If a "close to optimal" solution is good enough, then pick_move could be modified to use Alpha Beta Pruning to figure out which of the "smart" moves looks like it's the smartest. I would guess a good scoring method would award one point to for each tape in the correct slot, and half a point if there's a tape in slot 0. (in which case something else is empty, and can be filled directly)

    #!/usr/bin/perl -wl use strict; sub smart_moves { my @slots = @{ shift(@_) }; my @from; my $to; for (my $i = 0; $i < scalar(@slots); $i++) { if (0 != $i and 0 == $slots[$slots[$i]]) { # only one smart move if the home for the tape # in slot i is empty return ( [ $i, $slots[$i] ] ); } if (0 == $slots[$i]) { $to = $i; next; } # don't move anything that's allready 'home' push @from, $i unless $i eq $slots[$i]; } return map { [$_ , $to ] } @from; } sub make_move { # returns the new @slots after the move my @slots = @{shift(@_)}; my @move = @{shift(@_)}; $slots[$move[1]] = $slots[$move[0]]; $slots[$move[0]] = 0; return @slots; } sub pick_move { my @slots = @{shift(@_)}; # current configuration my @history = @{shift(@_)}; # moves made so far my @moves = smart_moves(\@slots); return @history if 0 == scalar @moves; my @best; foreach (@moves) { my @s = make_move \@slots, $_; my @h = @history; # copy it push @h, $_; my @result = pick_move(\@s, \@h); if (0 == scalar(@best) || scalar(@result) <= scalar(@best)) { @best = @result; } } return @best; } my @slots = @ARGV; my @done = pick_move(\@slots, []); foreach (@done) { print join(",", @slots) . "\t$_->[0] => $_->[1]"; @slots = make_move(\@slots,$_); } print join(",", @slots) __END__ laptop:~> monk.pl 0 2 1 0,2,1 2 => 0 1,2,0 1 => 2 1,0,2 0 => 1 0,1,2 laptop:~> monk.pl 0 1 2 0,1,2 laptop:~> monk.pl 0 2 1 4 5 3 0,2,1,4,5,3 5 => 0 3,2,1,4,5,0 4 => 5 3,2,1,4,0,5 3 => 4 3,2,1,0,4,5 2 => 3 3,2,0,1,4,5 1 => 2 3,0,2,1,4,5 3 => 1 3,1,2,0,4,5 0 => 3 0,1,2,3,4,5 laptop:~> monk.pl 0 2 1 7 8 9 5 4 3 6 0,2,1,7,8,9,5,4,3,6 9 => 0 6,2,1,7,8,9,5,4,3,0 5 => 9 6,2,1,7,8,0,5,4,3,9 6 => 5 6,2,1,7,8,5,0,4,3,9 8 => 6 6,2,1,7,8,5,3,4,0,9 4 => 8 6,2,1,7,0,5,3,4,8,9 7 => 4 6,2,1,7,4,5,3,0,8,9 3 => 7 6,2,1,0,4,5,3,7,8,9 6 => 3 6,2,1,3,4,5,0,7,8,9 2 => 6 6,2,0,3,4,5,1,7,8,9 1 => 2 6,0,2,3,4,5,1,7,8,9 6 => 1 6,1,2,3,4,5,0,7,8,9 0 => 6 0,1,2,3,4,5,6,7,8,9
Re: Re: sort with fewest moves (Bose-Nelson algorithm)
by axelrose (Scribe) on Feb 11, 2002 at 19:38 UTC

    Many thanks to you and all the others for the many and sound responses!

    After all I understand that I should have named it "minimal move algorithm"

    I need some time to digest all of this. For the moment I'll leave the monastery for the German Perl workshop which starts tomorrow evening:)
    Cheers, Axel.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://144611]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2022-01-26 21:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (70 votes). Check out past polls.

    Notices?