wu :: forums
« wu :: forums - Alphabetize my DVD's »

Welcome, Guest. Please Login or Register.
Mar 4th, 2024, 2:44am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: ThudnBlunder, towr, Icarus, william wu, Eigenray, SMQ, Grimbal)
   Alphabetize my DVD's
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Alphabetize my DVD's  (Read 2569 times)
BMAD
Junior Member
**





   


Posts: 57
Alphabetize my DVD's  
« on: May 23rd, 2014, 2:53pm »
Quote Quote Modify Modify

My DVD Shelves used to be organized by genre and frequency of watching.  Now that I spend less time watching DVDs I find myself desiring to arrange these DVDs in alphabetical order.  I don't care if they are left to right OR right to left order, i am not that picky.  To arrange my DVDs with precision I will take one DVD off the shelf and place it in the correct spot back on the shelf.  If I have 11 DVDs what is the most moves I can expect to make?  What if I had two shelves of 11 DVDs each?
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Alphabetize my DVD's  
« Reply #1 on: May 23rd, 2014, 3:45pm »
Quote Quote Modify Modify

What are you doing if the place is occupied by another DVD? (And as I understand it, it should be, unless the DVD already was in its right place).
IP Logged
BMAD
Junior Member
**





   


Posts: 57
Re: Alphabetize my DVD's  
« Reply #2 on: May 23rd, 2014, 3:56pm »
Quote Quote Modify Modify

So Like if my dvd's were in the following order:
 
 
2, 4, 1, 3, 6, 7, 5
 
Say I pick DVD #5, I would then place it in the 5th place between 3 and 6, essentially move DVD's 6 and 7 to the 6th and 7th place respectively (without having to officially move them).
Resulting in
2, 4, 1, 3, 5, 6, 7
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Alphabetize my DVD's  
« Reply #3 on: May 24th, 2014, 12:48am »
Quote Quote Modify Modify

So basically we need to find what the minimum longest increasing (or decreasing) subsequence is, because then we can take that without changing it and insert the rest of the DVDs in the right place.
[edit]There's always at least 4 DVD that have the right order (according to my python script), so that gives an upper limit of 7 moves. But I'm not so sure anymore that can't be improved.[/edit]
 
For the two shelf case, can both shelves be sorted in different directions?
« Last Edit: May 24th, 2014, 4:04am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Alphabetize my DVD's  
« Reply #4 on: May 24th, 2014, 5:45am »
Quote Quote Modify Modify

Good point.
By the way, among N element, the longest monotone subsequence is at least sqrt(N) elements.  It confirms your result.
PS:
With 6 moves or less there must be 5 DVDs or more untouched.  This implies there is a monotone subsequence of length 5.  But it is not always the case.
So 7 moves the best you can guarantee.
« Last Edit: May 24th, 2014, 5:50am by Grimbal » IP Logged
BMAD
Junior Member
**





   


Posts: 57
Re: Alphabetize my DVD's  
« Reply #5 on: May 24th, 2014, 7:04am »
Quote Quote Modify Modify

Yes.  The shelves don't need to be organized in the same direction.
IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Re: Alphabetize my DVD's  
« Reply #6 on: May 25th, 2014, 5:09pm »
Quote Quote Modify Modify

When I am organising my DVDs, I often pick up two adjacent DVDs, and move them to a new place together in one move. I wonder, if you were able to do that in the 11 dvd puzzle, how much you could improve your result by?
 
And what if you weren't limited to 2, but could pick up any number of adjacent DVDs? (you'd never need to pick up more than 5 of course, since a move of 6 or more could be just as easily accomplished with a smaller move of different DVDs.
IP Logged
EdwardSmith
Junior Member
**





   
WWW

Posts: 61
Re: Alphabetize my DVD's  
« Reply #7 on: Jul 15th, 2014, 11:59pm »
Quote Quote Modify Modify

If you wanted all the DVDs in alphabetical order. Then the worst case would be a list in reverse order.
This would take n-1 moves
CBA987654321
1CBA98765432
12CBA9876543
etc
 
As you state that it doesent matter if the DVDs are in alphabetical or reverse order. I think the worst case would be 9 moves because you would have to decide which order you wanted them in on the first move.
 
With 2 rows of DVDs it would be 2 times this amount.
 
As you watch some DVDs more than 1 time this would take quite a while.
IP Logged


Schottland Pension
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: Alphabetize my DVD's  
« Reply #8 on: Jul 16th, 2014, 6:45am »
Quote Quote Modify Modify

on Jul 15th, 2014, 11:59pm, EdwardSmith wrote:
As you state that it doesent matter if the DVDs are in alphabetical or reverse order. I think the worst case would be 9 moves because you would have to decide which order you wanted them in on the first move.

 
That seems too high - if the shelf is in a really bad order for sorting into reverse order, it's in a good order for sorting into forward order; and vice versa.
 
Since it takes 10 moves to convert one order into the other, it takes at most 5 moves to reach one of the two orders when starting from something on (one of) the ten-move path(s) between the orders.
 
Quick calculation: there are n! possible orders for the shelf, while the sorting process moving r DVDs can only account for a certain number of initial derangements: you have 2 possible choices of final arrangement, n!/(r!(n-r)!) possible choices of DVDs to have moved, and n!/(n-r)! possible arrangements to have ended up with for that choice of which to move, so you can only accommodate at most 2n!n!/(r!(n-r)!(n-r)!) possible derangements - in practice it will be fewer since that counts all the times you only actually move fewer than r DVDs multiple times. Since you want that to be greater than the total number of possible derangements, you can rearrange to give:
 
2n! > r!(n-r)!(n-r)!
 
For n=11, r=5, we need:
 
2*39916800 > 120*720*720
79833600 > 62208000
 
So moving 5 DVDs is a plausible lower bound; moving 9 is an upper bound, and towr and Grimbal have already shown that the correct answer does indeed lie somewhere in between - towr by some sort of computer-search and Grimbal by calling on standard results.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Alphabetize my DVD's  
« Reply #9 on: Jul 16th, 2014, 9:53am »
Quote Quote Modify Modify

If the DVDs are in the following order
    9 5 1 10 6 2 11 7 3 8 4,
the longest monotonous subsequence has 4 elements.  
That means you can keep only 4 DVDs untouched and have to move the 7 remaining.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board