Author |
Topic: Alphabetize my DVD's (Read 2578 times) |
|
BMAD
Junior Member
Posts: 57
|
 |
Alphabetize my DVD's
« on: May 23rd, 2014, 2:53pm » |
 Quote  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: 
Posts: 7526
|
|
Re: Alphabetize my DVD's
« Reply #1 on: May 23rd, 2014, 3:45pm » |
Quote 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 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:
Posts: 13730
|
|
Re: Alphabetize my DVD's
« Reply #3 on: May 24th, 2014, 12:48am » |
Quote 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:
Posts: 7526
|
|
Re: Alphabetize my DVD's
« Reply #4 on: May 24th, 2014, 5:45am » |
Quote 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 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 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
Posts: 61
|
|
Re: Alphabetize my DVD's
« Reply #7 on: Jul 15th, 2014, 11:59pm » |
Quote 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
    
Gender:
Posts: 2872
|
|
Re: Alphabetize my DVD's
« Reply #8 on: Jul 16th, 2014, 6:45am » |
Quote 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:
Posts: 7526
|
|
Re: Alphabetize my DVD's
« Reply #9 on: Jul 16th, 2014, 9:53am » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print