wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Alphabetize my DVD's
        
(Message started by: BMAD on May 23^rd, 2014, 2:53pm)

Title: Alphabetize my DVD's
Post by BMAD on May 23^rd, 2014, 2:53pm

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?

Title: Re: Alphabetize my DVD's
Post by Grimbal on May 23^rd, 2014, 3:45pm

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).

Title: Re: Alphabetize my DVD's
Post by BMAD on May 23^rd, 2014, 3:56pm

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

Title: Re: Alphabetize my DVD's
Post by towr on May 24^th, 2014, 12:48am

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][hide]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.[/hide][/edit]

For the two shelf case, can both shelves be sorted in different directions?

Title: Re: Alphabetize my DVD's
Post by Grimbal on May 24^th, 2014, 5:45am

Good point.
[hide]By the way, among N element, the longest monotone subsequence is at least sqrt(N) elements. It confirms your result.[/hide]
PS:
[hide] 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.[/hide]

Title: Re: Alphabetize my DVD's
Post by BMAD on May 24^th, 2014, 7:04am

Yes. The shelves don't need to be organized in the same direction.

Title: Re: Alphabetize my DVD's
Post by dudiobugtron on May 25^th, 2014, 5:09pm

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.

Title: Re: Alphabetize my DVD's
Post by EdwardSmith on Jul 15^th, 2014, 11:59pm

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.

Title: Re: Alphabetize my DVD's
Post by rmsgrey on Jul 16^th, 2014, 6:45am

on 07/15/14 at 23:59:49, 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.

Title: Re: Alphabetize my DVD's
Post by Grimbal on Jul 16^th, 2014, 9:53am

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.