FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Row-column-row sort generalized to higher dimensions
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
jhnrmsdn@yahoo.co.uk
science forum addict


Joined: 25 Mar 2006
Posts: 68

PostPosted: Fri Jun 02, 2006 6:41 pm    Post subject: Row-column-row sort generalized to higher dimensions Reply with quote

Some years ago Martin Gardner discussed the problem of
sorting a rectangular squad of soldiers (each standing on
adjacent points of a square lattice as one would expect),
say, by height.

I think it turned out that if each row from front to back
shuffles into order independently, in the same direction
for all rows, and then each column does the same
independently (which may of course mess up the
rows), then after a second row-sort as before the
columns all remain sorted.

I'd be interested to confirm this recollection and if
anyone knows how, or whether, this generalizes to
higher dimensions, either by planes sorting or rows
sorting independently.
Back to top
Phil Carmody
science forum Guru Wannabe


Joined: 05 Jun 2005
Posts: 267

PostPosted: Fri Jun 02, 2006 7:09 pm    Post subject: Re: Row-column-row sort generalized to higher dimensions Reply with quote

jhnrmsdn@yahoo.co.uk writes:
Quote:
Some years ago Martin Gardner discussed the problem of
sorting a rectangular squad of soldiers (each standing on
adjacent points of a square lattice as one would expect),
say, by height.

I think it turned out that if each row from front to back
shuffles into order independently, in the same direction
for all rows, and then each column does the same
independently (which may of course mess up the
rows), then after a second row-sort as before the
columns all remain sorted.

I'd be interested to confirm this recollection and if
anyone knows how, or whether, this generalizes to
higher dimensions, either by planes sorting or rows
sorting independently.

2D sorting is mentioned in some of Dan Bernstein's writings
on efficient hardware implementation of NFS. Maybe some of
his references will be useful. http://cr.yp.to/djb/

Phil
--
The man who is always worrying about whether or not his soul would be
damned generally has a soul that isn't worth a damn.
-- Oliver Wendell Holmes, Sr. (1809-1894), American physician and writer
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Mon Dec 10, 2018 3:48 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Column chromatography puja Chem 0 Fri Jul 21, 2006 6:01 am
No new posts possible to use Generalized Method of Moments for this pr... comtech Math 1 Thu Jul 20, 2006 12:49 am
No new posts jordan decomposition and generalized eigenvectors Jeremy Watts Undergraduate 0 Tue Jul 18, 2006 6:49 pm
No new posts jordan decomposition and generalized eigenvectors Jeremy Watts num-analysis 3 Tue Jul 18, 2006 6:48 pm
No new posts Generalized Gaussian variable, nissim nabar Math 2 Thu Jul 06, 2006 12:22 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0118s ][ Queries: 16 (0.0021s) ][ GZIP on - Debug on ]