Using simple arrays to sort numbers by stacking them?

Question

This is a homework question (sorry, I know these are frowned upon), but neither I nor the teacher actually knows how to solve it efficiently, so I wanted to put it up here to see if the wonderful brains on SO could help us out.

An array of unspecified size is given, containing random numbers. It must be sorted into increasing order. Each element can be either moved to an adjacent empty space, or moved on top of an adjacent larger element. I need to write a method that returns the minimum number of moves needed to sort the given array.

The question has been labeled 'optional', since the teacher realized the problem was far too difficult, but I'm curious how it might be solved. Any suggestions for arrays of any size (it can be for arrays of length 3 for all I care) are appreciated.

EDIT: Thanks for pointing out that this was unclear. I'm using the array to represent a hypothetical real world situation. Let's use the example of coins: they are all laid out on a table in a row, and there are only a specified number of 'spaces' they can be put in. But they can be put on top of adjacent larger coins, or slide to an adjacent empty space (which has been vacated by a coin that had presumably moved on top of a pile).

Answer 1

EDIT: Given that everyone seems to be solving a different problem, I'll state the problem I'm solving (which I believe to be the correct one (don't we all?)): (using disks to hopefully make things easier to understand)

Given n piles, each containing exactly 1 disk each, order these disks in increasing order of size. The end result must have each pile containing 1 disk each. The only allowed operation is to move a single disk from the top of one pile to the top of an adjacent pile, subject to the constraint that no disk may be placed on top of a smaller disk. Moving a disk to an empty pile or moving the last disk from a pile is allowed. There are always n piles, thus: (1) New piles may not be created, so a disk may not be moved outside the bounds of the original sequence. (2) Empty piles remain, so if the adjacent position is empty, the disk may not be moved over that position without first being moved onto that position.

Note:

A disk with a diameter of x = a number x.

This may not be the most efficient solution, but it should work and may give someone something to work off of.

It's a purely iterative process - after every step we end with all stacks having size 1; this may be a fundamental inefficiency with this approach.

Solution:

I'll use 1, 2 and 5 to illustrate the below, but this is just to indicate size ordering, it holds the same for any other numbers with the same ordering.

• Repeat until sorted:
  • Find the biggest element not already in the correct position (5 in this case)
    
    • (Actually it doesn't have to be the biggest, just anything in the below form, but be careful not to move elements past where they should be)
  • We have 2 cases:
    • It's at the left-most position, we have 2 cases:
      • 512... - move 1 right, move 5 right, move 1 2 left, end with 152
      • 521... - move 1 2 left, move 2 right, move 1 2 right, move 5 right, move 1 2 left, end with 152
    • It's not at the left-most position, we have 2 cases:
      • ...251... - move 1 2 left, move 5 right, move 1 right, end with 215
      • ...152... - move 2 left, move 1 right, move 1 right, move 2 left, end with 251 (after which we do steps from previous case)

EDIT 2:

A more efficient solution:

1. Find the smallest disk not in the right position
2. Put it on top of the disk to the right
3. Shift all disks to the left of that disk 1 position right
4. Shift the smallest disk all the way to the left (until you encounter a smaller disk which would already be in the right place)

Possible preprocessing step: Sort to a separate list to efficiently find smallest elements

Optimization: If you were going to move a disk to the right past its target position, instead, don't shift the disk on the right to the right in the previous step, but simply put this disk on that disk. How to do this at the right time efficiently may be a bit complex. It may also be helpful to not perform certain moves to increase efficiency.

Example:

52413

// put smallest disk (1) on disk to the right
    1
524_3

// shift disks to the left 1 position right (3 moves - moved 4, then 2, then 5)
    1
_5243

// move 1 all the way left (4 moves)
15243

// same as above for 2

   2
15_43

   2
1_543

12543

When the smallest disk is on the right-most position (as is now the case with 3), this is a bit of a problem. 2 ways of resolving it:

• Swap 1 and 2 and put 1 on 2 (1 2 positions right, 2 left, 1 2 positions left). Then you'd have an open spot onto which to move 3. Not an option if there's less than 2 smaller elements. These elements shouldn't be fixed until we've sorted a few more elements, in case we run into the same situation.

• If we had 12453, we could simply put 4 on 5 to open a slot for 3 (which sort of delays the problem). If the first non-sorted disk (5 in this case) is bigger than the second one (4) we could use some strategy like I described for my previous solution above to move elements to satisfy this condition.

Answer 2

I decided to examine the problem with a few assumptions/changes, because it made it a more interesting problem to me:

1) You can move elements left or right from any part of a pile.

2) You can stack an element onto a pile no matter if it's bigger, smaller or the same size.

3) The array is considered sorted as long as you never encounter a bigger number before a smaller number no matter how you go through stacks. So _ 11 2 3 is sorted but _ _ 12 3 is not because you could interpret the 2 as being before the 1.

This leads to a very interesting problem, in spite of this axiom:

Axiom A: The order in which you make moves is irrelevant, and can be re-arranged in any way to still achieve the same final result.

Axiom Ab: If the array has no repeats in it, then simply move every element towards its final position.

In particular, I developed a strategy hoping that you could solve it with only local examination and no recursiveness/backtracking, but I've proven that this is fruitless and will show it later.

My strategy is:

1) Proceed from left to right looking for pairs that are flipped the wrong way (a higher number before a lower number).

2a) When you find one, if there is an empty spot or a stack that the right hand value could immediately fill, move it left until it does fill it.

2b) Else, move the left value right one. This creates a situation where you have a stack of indifferent numbers - first, compare the value you moved right to the value on its new right according to the logic of 1) before comparing downwards.

2bii) Treat a downwards comparison the same way as a pair comparison - move the lower value left if it can fit an empty spot or stack, else move the higher value right and continue.

Examples:

1231 -> we shift 1b left because it will fit onto a stack. 11 2 3 _

1321 -> we shift 3 right because 2 will not fit into an empty spot/onto a stack. we shift 1b left twice because it will fit into an empty spot/fit onto a stack, then we shift 3 right because 2 will not fit into an empty spot/onto a stack. 1 1 2 3

1132 -> we shift 3 right as 2 can't go left. we shift 2 left because it will fit in an empty spot. 1 1 2 3

2311 -> we shift 3 right as 1a can't go left. we shift 1b left twice because it will fit in an empty spot. we shift 1a left because it will stack. we shift 2 right because 1a1b can't go left. we shift 1a2b left as it will fill an empty spot. 11 2 3 _

However, we run into a problem with these two starting arrays:

23411 10 moves optimal, 2r 3r 4r 1al*3 1bl*4 to make 11 2 3 4 _.

23111 9 moves optimal, 2r*3 3r*3 1bl 1cl*2 to make _ _ 111 2 3 - the opposite of the 23411 strategy! We move the 1s less and the 23 more because there are more 1s and so we save moves moving them as little as possible.

Which shows that we can't JUST do a simple local comparison to solve this new problem.

I'm still thinking about this problem, it seems non-trivial in an intriguing way, and I hope some of you enjoy contemplating this with me :)

Answer 3

I assume:

• "sorted" means there is a single stack left
• we can only move a stack onto another stack if the largest number in the source stack is smaller than the smallest number in the destination stack (or equivalently: stacks must be sorted with smaller numbers on top, and moving a stack onto another moves the entire stack on top of the other)

Then, there is obviosly no solution if the array contains a number more than once. Also, the magnitude of the numbers doesn't matter, only their rank does. Without loss of generality, we can therefore assume that the array contains the numbers 1..n in arbitrary order. Also, to determine the possible moves, only the top of bottom of the stacks matter. It is therefore sufficient to store:

int[] bottom;
int[] top;

Since we can not take stacks apart, we may only move stack i onto stack j if bottom[i] + 1 == top[j], or we'll end up in an unsolvable state. If however, we are in a game state where such a move is possible, it is optimal to perform it immediately, because eventually we'll have to combine these stacks, and moving an individual stack around is cheaper than moving two stacks around.

The only degree of freedom therefore is how to move the stacks into position with the least number of moves. At this time, I don't see an obvious greedy algorithm for that, so finding the optimal solution may require encoding the positions of the game into a graph, and apply a shortest path algorithm to that graph to find the shortest sequences of moves.