Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
Author Message
jhnrmsdn@yahoo.co.uk
science forum addict

Joined: 25 Mar 2006
Posts: 68

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

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.
Phil Carmody
science forum Guru Wannabe

Joined: 05 Jun 2005
Posts: 267

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

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
Google

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Mon Feb 18, 2019 7:46 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Column chromatography puja Chem 0 Fri Jul 21, 2006 6:01 am possible to use Generalized Method of Moments for this pr... comtech Math 1 Thu Jul 20, 2006 12:49 am jordan decomposition and generalized eigenvectors Jeremy Watts Undergraduate 0 Tue Jul 18, 2006 6:49 pm jordan decomposition and generalized eigenvectors Jeremy Watts num-analysis 3 Tue Jul 18, 2006 6:48 pm 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.0122s ][ Queries: 16 (0.0020s) ][ GZIP on - Debug on ]