Alphabetize my Dvd's

[BMAD]

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, 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?

[bonanova]

Look at the matrix of situations in this link.

http://www.sorting-algorithms.com/

There are eight columns, representing eight sorting algorithms.

There are four rows, representing four different initial orderings.

Tap the green arrows in the upper left corner.

Each cell shows a sort process that requires a certain number of moves.

If we hypothetically insert a row for EVERY initial ordering,

We would get a row of eight numbers for each of them.

The number in which cell represents the answer to the OP?

[gavinksong]

Look at the matrix of situations in this link.

http://www.sorting-algorithms.com/

There are eight columns, representing eight sorting algorithms.

There are four rows, representing four different initial orderings.

Tap the green arrows in the upper left corner.

Each cell shows a sort process that requires a certain number of moves.

If we hypothetically insert a row for EVERY initial ordering,

We would get a row of eight numbers for each of them.

The number in which cell represents the answer to the OP?

Unfortunately, no. Keep in mind that these are computer algorithms.

First of all, you can't really get a "number of moves" from a computer algorithm.

Also, not all of these algorithms follow the conditions described in the OP. For example, quicksort and mergesort recursively divide the set into subsets and then recombine them. Heapsort and shellsort repeatedly swap entries until the set is ordered. Only insertion sort and bubblesort (and perhaps selection sort if it is implemented unusually) make valid "moves" as they are defined in the OP, which is that an item is repeatedly taken and moved to a new place (in between two other items) - and none of these algorithms are efficient in most cases.

That being said, none of these algorithms are guaranteed to make the most efficient moves.

These computer algorithms are only optimal for sorting abstract data structures in the shortest amount of time but not in the smallest number of "moves." Making a "move" (ie. swapping or moving entries) for a computer is inexpensive and will be done often in order to simplify the problem even if it is not part of the most efficient solution (by which I mean solution with the fewest moves).

I guess a better way to think of it would be if a computer had to calculate how to optimally sort an arrangement of physical items where making a "move" was extremely expensive. For example, if we were sorting heavy storage containers.

[BMAD]

Gavinnksong

Do you agree with these notions for this problem:

1. Even sets have a max of n/2 moves to sort given the wose possible disarray of DVDs.

2. Odd sets either have n/2 +/- 1 moves to sort given the wose possible dissarray

3. WLOG, The worst possible disarray apears the reversing of dual-consecutive number where if there are k terms and k is odd the kth term goes in the middle.

Example of #3:

1-K terms where k is even

2,1 , 4,3 , 6,5 , ... , k, k-1

1-k terms where k is odd

2,1 , 4,3 , 6,,5 , ...n, n-1, k, n+2, n+1, ... k-1, k-2

Edited July 25, 2013 by BMAD

[Pickett]

First of all, you can't really get a "number of moves" from a computer algorithm.

Umm...what? I mean, if there is a repeatable pattern that you follow in order to solve a problem, which in the case of the OP there is, then you can write a computer program to solve it (that's what programs are...repeatable steps)

From my understanding of the OP (and forgive me, because I may have missed something in the intermediate posts), the way this sort works is basically you grab a DVD, you KNOW what position it should be in, and you insert it there. So for example:

Define this as a single "move":

Look at a DVD...does it belong at the beginning of the list of DVDs? If not, take it out...shift all of the DVDs between its old position and its new position over and insert it at its correct spot.

Now the OP also says they don't care about ascending or descending order...whichever takes fewer of the above moves (but WORST case...in other words, take the WORST POSSIBLE permutation of the DVDs using the above sort, and figure out the fewest number of "moves" it would take to sort them either ascending or descending...that is the REQUIRED number of moves to ENSURE you have sorted them.)

If I understood, and described the OP correctly, then here are the results for 1-11 DVDs:

#DVDs # required moves

1 0

2 0

3 1

4 2

5 2

6 3

7 3

8 4

9 4

10 5

11 5

I didn't go out further, as it becomes pretty CPU intensive to get all possible permutations for 12 objects (479,001,600 possible permutations if my math serves me right...), and then to SORT all of those both ascending and descending using the described sorting "move"...

[Pickett]

I may have a small error in my code, I need to double check the results above...

[BMAD]

First of all, you can't really get a "number of moves" from a computer algorithm.

Umm...what? I mean, if there is a repeatable pattern that you follow in order to solve a problem, which in the case of the OP there is, then you can write a computer program to solve it (that's what programs are...repeatable steps)

From my understanding of the OP (and forgive me, because I may have missed something in the intermediate posts), the way this sort works is basically you grab a DVD, you KNOW what position it should be in, and you insert it there. So for example:

Define this as a single "move":

Look at a DVD...does it belong at the beginning of the list of DVDs? If not, take it out...shift all of the DVDs between its old position and its new position over and insert it at its correct spot.

Now the OP also says they don't care about ascending or descending order...whichever takes fewer of the above moves (but WORST case...in other words, take the WORST POSSIBLE permutation of the DVDs using the above sort, and figure out the fewest number of "moves" it would take to sort them either ascending or descending...that is the REQUIRED number of moves to ENSURE you have sorted them.)

If I understood, and described the OP correctly, then here are the results for 1-11 DVDs:

#DVDs # required moves

1 0

2 0

3 1

4 2

5 2

6 3

7 3

8 4

9 4

10 5

11 5

I didn't go out further, as it becomes pretty CPU intensive to get all possible permutations for 12 objects (479,001,600 possible permutations if my math serves me right...), and then to SORT all of those both ascending and descending using the described sorting "move"...

This is interesting. It seems to support the n/2-1 conjecture mentioned earlier. Is there a way to see the solution (or shifts made) to the 11 dvd problem organized like gavinksong did?

[Pickett]

Ok, so I think I mis-interpreted the OP...it states:

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 that's the case, let's look at the example of 2, 4, 1, 3:

Start with 1...move it to its correct spot (and shift as needed): 1, 2, 4, 3...then try 2...it's already there...then 3, and move it...1, 2, 3, 4...you're done.

However, you can also do this by moving the 2 between 1 and 3 initially:

2, 4, 1, 3 --> 4, 1, 2, 3 --> 1, 2, 3, 4...

Which of the above is what you would expect from your OP? Either way, my numbers are not correct, and I need to change them...I will probably do that tomorrow and post my results.

[BMAD]

Ok, so I think I mis-interpreted the OP...it states:

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 that's the case, let's look at the example of 2, 4, 1, 3:

Start with 1...move it to its correct spot (and shift as needed): 1, 2, 4, 3...then try 2...it's already there...then 3, and move it...1, 2, 3, 4...you're done.

However, you can also do this by moving the 2 between 1 and 3 initially:

2, 4, 1, 3 --> 4, 1, 2, 3 --> 1, 2, 3, 4...

Which of the above is what you would expect from your OP? Either way, my numbers are not correct, and I need to change them...I will probably do that tomorrow and post my results.

In terms of practicallity, they both provide satisfactory results. I think it would depend on the arrangement of the dvds. In your case, both produced two moves so it doesn't matter but I am unsure if that will be the case in larger samples and in all arrangements. Is there a way to set it up where both strategies run and the one with the better score be kept?

[gavinksong]

Pickett,

I apologize for the hasty wording in my previous post. Of course, a computer program takes a measurable number of "steps" - once you define the term "step." You could count at the binary level, you could count the number of times you read or write a value, you could count the number of times you iterate through a specific loop, you could count the levels of recursion of achieved by a specific function, or you could count something slightly more arbitrary, such as the number of times you move an entry to another place in the list and then shift everything over. My post was in response to a post that suggested that we looked at the several sorting algorithms (including insertion sort, bubble sort, merge sort, shell sort, and quicksort), and there was a link to a website comparing the running times of these algorithms. I was simply saying that we would have to look at the number of "steps" made rather than at the running times, but that a "step" would be difficult to define in many of these sorting algorithms, especially since in some of these algorithms work by repeating a basic action that does not fulfill the requirements for a valid "step" as described in the OP. One example would be mergesort, which divides the set into two sublists, recursively applies mergesort on them, and them merges them together by repeatedly comparing the two lowest elements (one from each sublist) and then moving the lower element back onto the original list.

Also, as I understand it, the OP does not specify an algorithm for sorting the DVDs. It must just be assumed that the individual somehow makes the fewest number of moves before achieving order (or if it helps to think of it this way, the best algorithm for any arrangement rather than the same algorithm for all). We can ask BMAD to clear this up, but even if it is wrong, my interpretation would also make a pretty interesting problem.

If we follow your algorithm (as I understand it), then with the following arrangement of 11 DVDs:

BADCFKEHGJI

ABDCFKEHGJI (move A to the first position)

ABCDFKEHGJI (move C to the third position)

ABCDEFKHGJI (move E to the fifth position)

ABCDEFGKHJI (move G to the seventh position)

ABCDEFGHKJI (move H to the eight position)

ABCDEFGHIKJ (move I to the ninth position)

ABCDEFGHIJK (move J to the tenth position)

We make 7 moves. However, there is a simpler solution:

BADCFKEHGJI

ABDCFKEHGJI (move B to before A)

ABCDFKEHGJI (move C to before D)

ABCDEFKHGJI (move E to before F)

ABCDEFKGHJI (move G to before H)

ABCDEFKGHIJ (move I to before J)

ABCDEFGHIJK (move K to the end)

This only takes 6 moves, and I would say that it cannot take less then 6, regardless of what sequence of moves we make or what algorithm we follow. However, I have no proof, and I think that is the problem.

Edited July 26, 2013 by gavinksong

[gavinksong]

Gavinnksong

Do you agree with these notions for this problem:

1. Even sets have a max of n/2 moves to sort given the wose possible disarray of DVDs.

2. Odd sets either have n/2 +/- 1 moves to sort given the wose possible dissarray

3. WLOG, The worst possible disarray apears the reversing of dual-consecutive number where if there are k terms and k is odd the kth term goes in the middle.

Example of #3:

1-K terms where k is even

2,1 , 4,3 , 6,5 , ... , k, k-1

1-k terms where k is odd

2,1 , 4,3 , 6,,5 , ...n, n-1, k, n+2, n+1, ... k-1, k-2

That would be my guess.

Although for number 3, we would have to clarify, since we are not sure, that it is not the (unique) worst possible disarray but one of the worst possible disarrays (as in, the set of worst possible disarrays contains several arrangements since one other example would simply be the reverse, and there may be more). Perhaps one requirement for WPDs are that they are symmetrical?

And my guess for number 2 would be that we only round down until n=6 or n=7 (this is rather arbitrary since we don't have to round for n=6 since it is even), but we have no proof.

Edited July 26, 2013 by gavinksong

[gavinksong]

I should also mention that quicksort often relies on choosing a random pivot, so the number of moves it makes is in fact random (although its average runtime is statistically fast), which is another reason why it would be difficult to count the number of steps.

[Pickett]

So I agree that in certain sorting algorithms, defining a "step" would be difficult...however, I think with regards to this problem from a practical standpoint, I don't think it's very difficult. A "move" or "step" is simply when you physically grab a DVD and place it in a new position on the shelf...doesn't matter how you do it. In my opinion, if you were to "swap" two DVDs on the shelf (move first to last and last to first)...to me, that is TWO moves, not one. If you decided to do a merge sort on a shelf of DVDs, I would say you are doing a TON of extra moves...while it may be more efficient in computational time, to truly do it in practice, you would be moving DVDs all over the place on the shelf before finally getting them in order (unless you're a savant that can do layers and layers of recursion in your head and just do the final moves at the very end, in which case, my hat goes off to you...).

Now with your scenario above, what you said makes complete sense...which is where I think the clarification of the OP is required...because I ran into that same scenario...however, in your SECOND solution, you did not place a DVD in it's "correct spot" on the shelf...which goes against how I interpreted the OP (when you move G to before H...that is not the "correct" place on the shelf for G...). So by reading the OP as saying "I take a single DVD off the shelf and put it in its correct place, aka index, on the shelf...and repeat this until they are sorted either ascending or descending" (which is how I took it), you definitely have an algorithm with well defined "moves". It becomes very similar to a basic selection sort (although not exactly)...An example that is similar to what you have above, which still shows the difficulty of writing the algorithm to be "smart" is the following arrangement EBCAD:

OPTIMAL:

EBCAD

AEBCD (take "A" and move to index 0...yes, I'm 0-based)

ABCDE (take "E" and move to index 4)

2 moves total, and followed the OP as I read it...but this required some intuition/looking ahead to realize it could be done like that...where as a typical "sorting algorithm" has to go methodically through it like the following:

SELECTION SORT:

EBCAD

AEBCD (take "A" and move it to index 0)

ABECD (take "B" and move it to index 1)

ABCED (take "C" and move it to index 2)

ABCDE (take "D" and move it to index 3)

4 moves...

To me, it's these constraints that make this puzzle very interesting and fun to think through programmatically. So I definitely agree that my answers that I posted before are not completely correct...I have a few things I still need to work out in the algorithm...It's starting to look like I'll need some heuristics in order to find optimal paths...of course it's very possible that I am WAY overthinking this whole thing and I'm just using it as an excuse to do something else while I'm at work ...except I'm still coding, which is what I do all day at work anyways ...

[BMAD]

Clarification on the op:

We are assuming that the user has knowledge of every possible sorting algorithm at hand. Armed with this knowledge there will still be a minimum number of 'steps' needed to fix the dvds. We seek to find this minimum number assuming that there is a universal worse case configurationn of dvds.

Universal in the sense that if an algorithm is applied to this array it would take more moves to fix (or equal to) than any other array.

[gavinksong]

Some interesting observations from an different viewpoint...

You can construct a graph where the vertices represent the different possible orderings and the edges represent moves. Two vertices are connected by an edge if you can travel between them by executing a single move.

For example, the graph for N=3 would look like an octahedron. ABC would be connected by an edge to CAB, ACB, BAC, and BCA - but not CBA since it takes two moves to go from ABC to CBA. It is easy to see here that the greatest "distance" from any vertex of the octahedron to ABC or CBA (which are always on opposite sides of the graph) is 1.

We can observe a couple of things about these graphs. We know that the number of vertices is always N! and that the number of edges radiating from any vertex is always (N-1)². We can also guess that reverse orderings are always on "opposite" sides and that the minimum number of moves it takes to reverse an ordering is always N-1.

Let's look at N=4, starting at ABCD. We know that ABCD is connected to (4-1)² = 9 other vertices. We also know the same is true of its reverse, and we know that there is no overlapping because there should be at least 4-1 = 3 edges between reverses. This accounts for 20 out of 4! = 24 total vertices. Interestingly, this means that the remaining four vertices must consist the "worst case" set. These are BADC, BDAC, CADB, and CDAB (which are apparently connected in the shape of a square).

Now for N=5. ABCDE is connected to (5-1)² = 16. If we count up these vertices and their mirrors, we find that we have accounted for 34 out of the 5! = 120 total vertices. If we assume that the worst possible scenario in N=5 forces us to make at least 2 moves, we must conclude that the remaining 86 vertices must make up the "worst case" set, which is a surprisingly large number.

An interesting note about the "worst case" set is that each member's reverse must also a member of the set.

[BMAD]

Brilliant observation. So does the number of worst case scendarios increase in a pattern? Does this method tell us that each worst case is equivalently bad regardless of algorithm?

[gavinksong]

Brilliant observation. So does the number of worst case scendarios increase in a pattern? Does this method tell us that each worst case is equivalently bad regardless of algorithm?

Yup. This is a pretty clear way of seeing how, no matter what algorithm you follow, there is a minimum number of moves, or "distance", between any of the vertices in the "worst case" set and either of the "ordered" states. Unfortunately, I could only make a complete analysis of the graph for N=4 - but I am hoping that others could expand on this.

[CaptainEd]

I'm with Gavin--we are not talking about sorting algorithms--we already know a vector of final index numbers (or two vectors, one for forward sorted and one for backward).

I think we would like a logistical algorithm--one that requires the fewest Steps as defined clearly by Pickett: remove "i", slide some down, insert "i" in the "i-th" slot, slide some up

The OP doesn't require this, but the OP DOES request to know the maximum fewest steps for N DVDs.

I did exhaustively verify that every permutation of 12345 can be changed to either 12345 or 54321 in two Steps or less.

I'm struck at how hard even this seemingly easy problem is: I can't straighten out BAKFHJCIDGE in under 7 moves.

Nice problem, BMAD.

[CaptainEd]

A method and a couple of questions that might lead to a theorem:

A method (incompletely specified)
In the sequence, identify a subsequence of maximal length. List the remaining indexes. Move Only them (here you've got to find the right order of operation). The maximal length subsequence items will all simply slide into their rightful places, as the other items are removed/inserted.

For example, the case I couldn't solve in a prior post (BAKFHJCIDGE) has a maximal subsequence of KJIGE (in reverse). Reorder the remaining letters (how? don't have an algorithm yet) and the sequence of Steps is ABCDFH, resulting in KJIHGFEDCBA.

Two questions that might form the meat of a theorem:
( Q1 ) Is there always a maximal ordered subsequence of length floor(N / 2), forward or backward?
( Q2 ) Can there always exist a valid set of Steps from the string with the subsequence removed?

Edited September 25, 2015 by CaptainEd

[CaptainEd]

Now I doubt we can order them in N/2 steps 

Note on BMADs DVDs
I'm surprised if we can put them in order with N/2 moves. According to Erdos, a sequence of (N^2 +1) distinct numbers is certain to have an ordered subsequence of length (N+1), possibly increasing, possibly decreasing. So maximum guaranteed ordered subsequence is roughly Sqrt( length ). 
When we pick up N/2 DVDs and move them, we haven't disturbed the order of the other N/2. So, for our moves to succeed, these untouched DVDs must already be in increasing or decreasing order. But Erdos doesn't promise we will have more than sqrt(n). 

[CaptainEd]

Wrong again! N/2 is not ruled out! 

A better statement of the Erdos-Szekers theorem is
(r-1)(s-1)+1 elements has at least r increasing or s decreasing subsequence

so a number that is 1+composite has a monotone subsequence at least min(r,s)

So, for 11 = 5x2+1; r=6,s=3; has an increasing subsequence of 6 or a decreasing subsequence of 3, or vice versa.
So maybe n/2 IS achievable for any odd number!

Then the next question in my mind is: can we guarantee that there is a sequence of Steps on the other (ie, the out-of-monotone-sequence) DVDs that doesn't mess up the in-sequence DVDs.

[BMAD]

Pickett (or anyone), 
Try this sequence: AGDICFEBKJH

Hidden Content

yeah so far, i can't get it in under 7 moves 

[CaptainEd]

Better bound, but not certain yet...

I have a clearer handle on the size of a monotone subsequence of the DVDs. The "pigeonhole principle" proof of the Erdos-Szekeres theorem shows that the longest monotone subsequence of N distinct numbers (or DVD titles) is ceil(sqrt( N )).
So, for 11 DVDs, the longest you can be sure of is 4 items already in order (increasing or decreasing). 

This would seem to imply that the answer to BMAD's challenge is ( N - ceil(sqrt( N ))). But I can't see clearly that that can always be achieved.

The implication for BMAD's challenge is this: she required that a Move consists of ( a ) remove a DVD, ( b ) insert it IN ITS PROPER PLACE. Pickett and I interpret this as follows: If the final location of a particular DVD is immediately after 4 DVDs, a Move consists of ( a ) remove the DVD and ( b ) insert it directly after 4 DVDs.

The problem remaining in my mind is:  Can we be sure that there is always a sequence of Moves that doesn't block one of the already-ordered items out of position. Do we sometimes have to move a DVD more than once? Do we sometimes have to move one of the items of the monotone subsequence?

[BMAD]

I don't know if this helps but:

I found the following relationships when considering from A to Z:

Moves required  = mr

Frequency = f

Mr  f

0 1

1 7

2 15

3 35

4 35

5 15

6 7

7 1

 

 

 

[gavinksong]

On October 4, 2015 at 4:30 AM, CaptainEd said:

Spoiler

When we pick up N/2 DVDs and move them, we haven't disturbed the order of the other N/2. So, for our moves to succeed, these untouched DVDs must already be in increasing or decreasing order.

 

This makes a lot of sense. The fewest number of moves to sort a sequence must be at least the length of the sequence minus the length of the largest monotone subsequence. At the same time, if you have a monotone subsequence of a certain length, then you can simply move the remaining DVDs into place. In other words, the fewest number of moves to sort a sequence is exactly the length of the sequence minus the length of the largest monotone subsequence.

On October 14, 2015 at 2:43 AM, CaptainEd said:

Spoiler

I have a clearer handle on the size of a monotone subsequence of the DVDs. The "pigeonhole principle" proof of the Erdos-Szekeres theorem shows that the longest monotone subsequence of N distinct numbers (or DVD titles) is ceil(sqrt( N )).
So, for 11 DVDs, the longest you can be sure of is 4 items already in order (increasing or decreasing). 

 

The captain is once again correct! When I revisited this thread, I immediately thought of the Erdos-Szekeres theorem as well. Each of the shelves containing BMAD's DVD collection must have a monotonic subsequence of at least length 4, which means the upper bound for minimum moves is 7. If we can find a sequence with no length 5 monotonic subsequence, then it should prove definitively that the maximum number of minimum moves to sort BMAD's collection is exactly 7.

Of course, CaptainEd's already beat us to the punch.

On October 9, 2015 at 1:27 AM, CaptainEd said:

Pickett (or anyone), 
Try this sequence: AGDICFEBKJH

Spoiler

This sequence of DVDs has no length-5 monotone subsequences. That means we will need at least 7 steps to put all the DVDs into an increasing or decreasing order.

 

I think the case is finally closed. Wouldn't you say? I've been awake for far too long. I need reassurance.

[Indra]

For the shelf with 11 DVD's, the most moves you would need are 9 moves.

For two selves, the most moves you may have to make are 19 moves.