Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

Alphabetize my Dvd's


  • Please log in to reply
39 replies to this topic

#21 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1826 posts
  • Gender:Female

Posted 24 July 2013 - 09:06 PM

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?
  • 0

#22 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 6145 posts
  • Gender:Male
  • Location:New York

Posted 24 July 2013 - 10:35 PM

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?


"Best moves" and "worst disarray" seem interrelated.
The worst disarray for one algorithm might be duck soup for another.

(Duck soup means easy - an Americanism.) :)
  • 0

Vidi vici veni.


#23 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1826 posts
  • Gender:Female

Posted 24 July 2013 - 11:25 PM

So are you saying that there isn't a best 'worst' disarray that regardless of algorithm will produce more moves than any other such disarray when comparing effect of said algorithm on both disarrays?


  • 0

#24 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 397 posts
  • Gender:Male
  • Location:i'm a bird

Posted 25 July 2013 - 02:45 AM

 

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?


"Best moves" and "worst disarray" seem interrelated.
The worst disarray for one algorithm might be duck soup for another.

(Duck soup means easy - an Americanism.) :)

 

 

Given that the individual always rearranges the DVDs in the most efficient way possible, what is the highest number of moves it takes for any initial arrangement? (The individual may not use the same algorithm on every arrangement. In fact, one should not assume that the individual follows any one algorithm at all).

 

Edit: From a previous post:

 

You are rearranging the shelf by repeatedly taking a DVD and moving to a new spot on the shelf, and we assume that you will always rearrange the shelf in the most efficient way possible (fewest number of moves) and that you will order them left-to-right or right-to-left depending on which is faster. The problem is to find the initial order of DVDs that will result in the most number of moves.


Edited by gavinksong, 25 July 2013 - 02:51 AM.

  • 0

#25 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 6145 posts
  • Gender:Male
  • Location:New York

Posted 25 July 2013 - 10:28 AM

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?
  • 0

Vidi vici veni.


#26 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 397 posts
  • Gender:Male
  • Location:i'm a bird

Posted 25 July 2013 - 01:07 PM

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


  • 0

#27 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1826 posts
  • Gender:Female

Posted 25 July 2013 - 01:22 PM

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, 25 July 2013 - 01:25 PM.

  • 0

#28 Pickett

Pickett

    Senior Member

  • Members
  • PipPipPipPip
  • 546 posts
  • Gender:Male
  • Location:40°N 83°W +/-10'

Posted 25 July 2013 - 06:52 PM

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

 

Spoiler for My quick and dirty algorithm

 

 


  • 0

#29 Pickett

Pickett

    Senior Member

  • Members
  • PipPipPipPip
  • 546 posts
  • Gender:Male
  • Location:40°N 83°W +/-10'

Posted 25 July 2013 - 07:14 PM

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


  • 0

#30 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1826 posts
  • Gender:Female

Posted 25 July 2013 - 07:17 PM

 

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

 

Spoiler for My quick and dirty algorithm

 

 

 

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




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users