wu :: forums « wu :: forums - Alphabetize my DVD's » Welcome, Guest. Please Login or Register. Sep 17th, 2024, 2:03pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: Grimbal, SMQ, towr, Icarus, william wu, ThudnBlunder, Eigenray)    Alphabetize my DVD's « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Alphabetize my DVD's  (Read 2588 times)
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: 7527
 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
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.
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: 7527
 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
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: 2873
 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: 7527
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »