• 0

Alphabetize my Dvd's

Question

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

39 answers to this question

  • 0

Posted (edited) · Report post

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 by BMAD
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by gavinksong
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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. :thumbsup:

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 by gavinksong
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 :duh:...

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.