Topic: A sorting problem (Read 1825 times)

ed boy · « **on:** October 27, 2014, 05:52:28 am »

I know there are algorithms for lots of sorting problems, but I can't find one for this problem. The sorting algorithms I have found are more for finding the correct order instead of how to achieve the correct order.

Suppose I have some cards, each with a number written on them (there may be duplicates) and N piles where cards can be placed. At the start, all the cards are in some known order in pile 1. My desired end state is to have all the cards in pile N in ascending order of the number written on them.

In order to achieve this, I have a robot that can pick up the top card from any pile and put it on the top of any other pile. However, doing so takes time, so I want to have as few operations as possible.

I have been able to work out some decent algorithms by myself, but I was wondering if this was a problem with a known best solution, or a known really good solution.

Thief^ · « **Reply #1 on:** October 27, 2014, 06:44:04 am »

This sounds like the Towers of Hanoi

gimlet · « **Reply #2 on:** October 27, 2014, 08:57:56 am »

Are the values and the order of the cards visible before time? Or are they face down and only examined when the robot picks them up? If they are face down, do you know the minimum and maximum values and average distribution of the values beforehand?

If they're all visible/known, then yeah that's a slightly different problem than most sorts try to optimize - you can create a plan before even doing the 1st physical operation.

I'd still be tempted to say "just look at all the variations of heap sort and pick a likely one".

As a quick guess for the cases where at least the min/max/distribution is known, I'd say - (let the total number of cards be C) distribute the lowest C/N cards in N1, the next lowest batch in N2, etc Then start on pile N1 and do the same thing, using the tops of piles N2-Nn as the temp workspace. One obvious tweak being you could start putting cards right on the output when you know they're the lowest.

Actually as soon as you've done the 1st distribution, the values/placement of the cards are then known, and you could calculate the optimal plan to sort them from that point. Depending on how expensive calculating a proposed sort is vs the physical operation, it *might* even be worth comparing every valid sorting plan to find the one with least total cost, or at least calculating enough of them until you find one within X% of the least possible total cost.

Hmm interesting...

ed boy · « **Reply #3 on:** October 27, 2014, 09:57:30 am »

Quote from: Thief^ on October 27, 2014, 06:44:04 am

This sounds like the Towers of Hanoi

It's similar, except we have multiples piles, we can have objects in the stack in whatever order we want, and some objects are identical.

Quote from: gimlet on October 27, 2014, 08:57:56 am

Are the values and the order of the cards visible before time? Or are they face down and only examined when the robot picks them up? If they are face down, do you know the minimum and maximum values and average distribution of the values beforehand?

The values and order of the cards are known beforehand. We can also assume that we know what the correct final order will be, as the time it would take to compute the correct order will be negligible compared to the time it would take for the robot to move all the cards. It may avoid confusion to think of the problem as moving the cards from one known order to another known order, with multiple possibilities for the desired order (as some cards may have the same number on them).

Quote from: gimlet on October 27, 2014, 08:57:56 am

I'd still be tempted to say "just look at all the variations of heap sort and pick a likely one".

From what I can make out from the heapsort wouldn't work, as it treats swapping two cards as a cheap operation, whereas in this problem swapping two cards is actually very expensive (it would require 4+2x operations, where x is the number of cards above the lowest of the cards to be swapped). Furthermore, it wouldn't take advantage of the multiple piles available.

Quote from: gimlet on October 27, 2014, 08:57:56 am

As a quick guess for the cases where at least the min/max/distribution is known, I'd say - (let the total number of cards be C) distribute the lowest C/N cards in N1, the next lowest batch in N2, etc Then start on pile N1 and do the same thing, using the tops of piles N2-Nn as the temp workspace. One obvious tweak being you could start putting cards right on the output when you know they're the lowest.

my current best guess is similar, but I have no idea how good an algorithm it is, or if this is a problem that has been investigated before - most attempts at finding a sorting algorithm are algorithms that produce a sorted list from an unknown list of numbers, and don't have the same minimization criteria as this problem.

Spoiler: my current best guess (click to show/hide)

My current best plan is rather flawed, though. The stage of sorting the intermediate piles becomes a lot more problematic and time consuming when y>N². It also fails to use pile 1 after the initial distribution of the cards, which is a clear sign that it is not optimal.

Thief^ · « **Reply #4 on:** October 27, 2014, 10:36:43 am »

Here's my attempt, a kind of recursive merge sort: (much the same as what everyone else is saying)

Given N piles and all the cards on pile 1 in a known order, and a wanted order on pile N as the destination:
Split the cards into N-1 piles across piles 1 - N-1 (so leave the destination pile (N) empty)
For each pile, if not reverse-sorted, recurse this algorithm, (placing the temporary piles on top of whatever other piles exist, ignoring them, and using the original pile as both the starting pile and the pile left empty/final pile unlike the outer loop)
Gather the sorted piles onto the final pile in the desired order. Because all the piles are reverse-sorted and the destination is empty, this is a simple repeated selection of which top card you want to move to the destination pile

It's not optimal though, it doesn't exploit any pre-existing sorted-ness in the data, e.g. moving the cards 1-10 to another pile in the order 10-1 should be 10 moves, and moving 1-10 to another pile in the same 1-10 order should only be 20.

It should be possible to look at the "sortedness" of the pile in order to determine how much temp space is needed to operate optimally, and behave differently if there's enough room available for an optimal approach

ed boy · « **Reply #5 on:** October 29, 2014, 11:01:05 am »

I've been doing some more thinking on this problem, and one can find some good results for the case when N=3.

There exists a fairly simple solution where we simply transfer the cards between two piles, taking the one of top if it's what we want. The worst-case scenario for this is that for each card we have to move every other card to get access to it, which results in a worse case scenario of x(x+1)/2 moves. We can apply this algorithm no matter how many piles we have (as long as N is at least 3, which we will assume), so the optimal solution will require at most x(x+1)/2 moves. Similarly, in the best case scenario the input order is the reverse of the output order, so it requires x moves no matter what N is.

The simple N=3 solution involves moving cards from the top of one pile to the other until the desired card is on top. To give an example:

Spoiler: example (click to show/hide)

We can try to improve this by using the third pile. If we are moving a number of cards from pile 1 to pile 2, we can choose to put a card from pile 1 onto pile 3, then later put that card from pile 3 onto pile 2. This requires an additional card move, but also allows us to put the card anywhere we want in pile 2 closer to the top.

The question then arises of when we want to do this, which cards we want to do it to, and how much we want to displace the cards. First we shall note that the best place for a card to be is adjacent to the card that comes just before it in rankings. Whether we want it to be just above or just below depends on whether the cards will be in their current order or in reversed order when we come to put them into pile 3. If they are going to be in the same order, then we will want each card to be just below the one ranked before it. If they are not, then we will want each card to be just above the one ranked before it. The number of moves that we save is the number of places shifted minus one.

Note that we can shift multiple cards in this manner. If we identify two cards that we would like to shift, we may be able to do both in the same operation. If card A would go onto pile 3 before card B, and card B would leave the pile before card A then we can shift both in the same operation. Note also that the longer the chain of cards to be shifted in one operation, the more opportunities we will have to shift cards, and therefore the larger the opportunity to save card movements.

There is a problem in the above, though - sometimes we would wish to shift two cards in one operation, but we cannot do both. This can occur if card A would go onto pile 3 before card B and also leave before card B. In this case, we have to choose which of the two to go for. This can get rather complicated, especially when we attempt to shift multiple cards in one operation.

Our superior algorithm is therefore as follows:

-Identify which card should go on top of pile 3 next
-Of piles 1 and 2, identify which have a copy of this card. If both do, select the one such the that bottommost copy of the card has fewest underneath it
-In the chosen pile, identify the topmost copy of the desired card. This card and all of the cards above it form the chain of cards that will be moved in this operation
-Within the chain, identify the pairs of cards that are numerically adjacent but are not physically adjacent. This is the list of opportunities to save card movements.
--We will want the cards in each pair to end up adjacent to each other. The order in which the pair should end up is to achieve the smallest distance between the largest of the pair and the physically nearest numerically subsequent card or the smallest distance between the smaller of the pair and the physically nearest numerically precedent card.
-Identify the best collection of pairs that can be shifted within the same operation. This can be complicated.
-Move the chain from one pile to the other, shifting cards when appropriate.
-repeat

We can reuse the same examples from earlier with this new algorithm.

Spoiler: new examples (click to show/hide)

I'm rather happy with this algorithm for the three-pile scenario. I feel like the method of choosing which cards to shift when some are mutually exclusive is another interesting problem (with the potential for partial movements over multiple operations). Expanding the problem to one of multiple piles, however, remains rather complicated.

Crashmaster · « **Reply #6 on:** October 31, 2014, 01:15:32 pm »

I can't say I fully grasp your problem but when I had to do some hand-filing of a large stack of unsorted invoices the trick I used was to sort them into ascending order first;

First pass the stack is sorted into ten piles based on the ones digit.
Piles re-stacked 0's on top 9's on bottom.
Stack is flipped over or drawn from the bottom for the second pass.
Second pass sorted again into ten piles based on tens digit - while sorting the 10's the 1's digits come up in descending order.
Piles as re-stacked again with 00's on top and 90's on bottom.
Stack is flipped over or drawn from the bottom again.
ten piles based on hundreds digit
Last re-stack 000's on top and 900's on bottom.
Repeat as needed for larger numbers and your stack of files should end up in numerical order regardless of missing or duplicate entries.

There needs to be several hundred items to be sorted before this becomes efficient at all but it is easier on the brain.
Turning over each card as it is sorted into a pile keeps the numbers up when you flip the wholes stack.

ed boy · « **Reply #7 on:** October 31, 2014, 05:55:41 pm »

I've been thinking some more on the problem, and I've come up with an algorithm that I feel pretty good about.

First, let us introduce a definition - we say that a sequence of cards is sortable with N piles if we can partition it into N-1 monotone subsequences. This can be proves somewhat easily - if the cards start in pile 1, we can put a subsequence into piles 2 through N, with at least one pile (1) empty. Note also that if we move a subsequence into an empty pile, the new pile contains the same subsequence, but in reversed order. This allows us to transfer cards between piles until all of the subsequences are in the same order. At that point, each pile will contain a monotone sequence of cards in the same order, and there will be at least one empty pile, so we can sort all the cards into the empty pile in monotone order. If this is not the monotone order we want, we can transfer it to another pile to put it into the order we want.

The algorithm is as such:
-Find the largest number of cards off the top of the original pile that form a sortable sequence
-Sort that sequence, and put the sorted cards into an empty pile
-If there are no empty piles, consolidate piles 2 through N into one big sorted pile
-repeat this process until there are no cards left in pile 1
-Consolidate all the piles into one big pile containing everything

The problem in this case is determining how many cards we can get into a sortable sequence. Note that it is sufficient to be able to verify if a given sequence of cards is sortable, as we can then try with progressively larger numbers.

What is bay12's opinion on this algorithm? Does anybody have any experience with the subsequence finding problem?

Bay 12 Games Forum

News:

Author Topic: A sorting problem (Read 1825 times)

ed boy

A sorting problem

Thief^

Re: A sorting problem

gimlet

Re: A sorting problem

ed boy

Re: A sorting problem

Thief^

Re: A sorting problem

ed boy

Re: A sorting problem

Crashmaster

Re: A sorting problem

ed boy

Re: A sorting problem