Reorder a collection of elements in minimum number of steps in C#

Question

I have a list of elements (namely PowerPoint slides) which I need to reorder in the minimal possible steps.

Each slide has an integer unique key (namely SlideID), and I can produce the required order of keys really fast, but actually moving a slide (executing a move) is relatively slow, as PowerPoint updates who-knows-what when it's called, therefore I try to execute the minimum amount of move commands.

So what I have is the list of keys in the original and the desired order, like:

int[] original = { 201, 203, 208, 117, 89 };
int[] desired = { 208, 117, 89, 203, 201 };

Looking around the internet I have concluded that finding the Longest Common Subsequence and moving everything else to the desired position would do what I need, so I implemented a T[] FindLCS<T>(T[] first, T[] second) method borrowing and adapting code from Rosetta Code.

For reordering the slides I have been provided a very limited API where I can only order by slide.MoveTo(int toPos). (Apart from this I can find a slide's Id by it's Index and vica-versa at any time.)

I have trouble implementing the remaining part, namely producing the actual list of moves I can execute since moving slide x will shift all slide indexes inbetween and I get confused over how to account for this.

Can someone help me produce a list of (int sourceIndex, int targetIndex) or (int id, int targetIndex) tuples I can simply iterate over?

Answer 1

Here is a greedy algorithm which selects the element to be moved according to the distance from the desired position:

static void Main(string[] args)
{
    int[] original = { 201, 203, 208, 117, 89 };
    int[] desired = { 208, 117, 89, 203, 201 };
    List<int> seq = new List<int>();
    int seqLen = original.Length;

    //  find initial ordering
    foreach(int io in original)
    {
        int pos = -1;
        for (int i = 0; i < desired.Length; i++)
        {
            if (desired[i] == io)
            {
                pos = i;
                break;
            }
        }
        seq.Add(pos);
    }

    showSequence(seq, "initial");
    //  sort by moving the entry which is off by the largest distance
    bool changed;
    do
    {
        changed = false;

        int worstPos = 0;
        int worstDiff = (0 - seq[0]) * (0 - seq[0]);

        for (int pos = 1; pos < seqLen; pos++)
        {
            int diff = (pos - seq[pos]) * (pos - seq[pos]);
            if (diff > worstDiff)
            {
                worstPos = pos;
                worstDiff = diff;
            }
        }

        if (worstDiff > 0)
        {
            //  move worst entry to desired position
            int item = seq[worstPos];
            seq.Remove(item);
            seq.Insert(item, item);
            changed = true;
            showSequence(seq, $"changed {item} from index {worstPos} to index {item}");
        }
    }
    while (changed);

    Console.WriteLine("ciao!");
}

private static void showSequence(List<int> seq, string msg)
{
    string s = "";

    foreach(int i in seq)
    {
        s = s + " " + i;
    }

    Console.WriteLine($"{msg}: {s}");
}

The algorithm stops as soon as all items are correctly placed.

---

Note that the algorithm is not necessarily optimal for all sequences.

Here is an example with 24 items:

initial:  14 0 15 22 6 8 20 21 18 17 9 7 19 1 23 12 11 5 2 16 13 3 4 10
1: changed 22 from index 3 to index 22:  14 0 15 6 8 20 21 18 17 9 7 19 1 23 12 11 5 2 16 13 3 4 22 10
2: changed 3 from index 20 to index 3:  14 0 15 3 6 8 20 21 18 17 9 7 19 1 23 12 11 5 2 16 13 4 22 10
3: changed 4 from index 21 to index 4:  14 0 15 3 4 6 8 20 21 18 17 9 7 19 1 23 12 11 5 2 16 13 22 10
4: changed 2 from index 19 to index 2:  14 0 2 15 3 4 6 8 20 21 18 17 9 7 19 1 23 12 11 5 16 13 22 10
5: changed 14 from index 0 to index 14:  0 2 15 3 4 6 8 20 21 18 17 9 7 19 14 1 23 12 11 5 16 13 22 10
6: changed 1 from index 15 to index 1:  0 1 2 15 3 4 6 8 20 21 18 17 9 7 19 14 23 12 11 5 16 13 22 10
7: changed 5 from index 19 to index 5:  0 1 2 15 3 5 4 6 8 20 21 18 17 9 7 19 14 23 12 11 16 13 22 10
8: changed 10 from index 23 to index 10:  0 1 2 15 3 5 4 6 8 20 10 21 18 17 9 7 19 14 23 12 11 16 13 22
9: changed 15 from index 3 to index 15:  0 1 2 3 5 4 6 8 20 10 21 18 17 9 7 15 19 14 23 12 11 16 13 22
10: changed 20 from index 8 to index 20:  0 1 2 3 5 4 6 8 10 21 18 17 9 7 15 19 14 23 12 11 20 16 13 22
11: changed 21 from index 9 to index 21:  0 1 2 3 5 4 6 8 10 18 17 9 7 15 19 14 23 12 11 20 16 21 13 22
12: changed 18 from index 9 to index 18:  0 1 2 3 5 4 6 8 10 17 9 7 15 19 14 23 12 11 18 20 16 21 13 22
13: changed 13 from index 22 to index 13:  0 1 2 3 5 4 6 8 10 17 9 7 15 13 19 14 23 12 11 18 20 16 21 22
14: changed 17 from index 9 to index 17:  0 1 2 3 5 4 6 8 10 9 7 15 13 19 14 23 12 17 11 18 20 16 21 22
15: changed 23 from index 15 to index 23:  0 1 2 3 5 4 6 8 10 9 7 15 13 19 14 12 17 11 18 20 16 21 22 23
16: changed 19 from index 13 to index 19:  0 1 2 3 5 4 6 8 10 9 7 15 13 14 12 17 11 18 20 19 16 21 22 23
17: changed 11 from index 16 to index 11:  0 1 2 3 5 4 6 8 10 9 7 11 15 13 14 12 17 18 20 19 16 21 22 23
18: changed 16 from index 20 to index 16:  0 1 2 3 5 4 6 8 10 9 7 11 15 13 14 12 16 17 18 20 19 21 22 23
19: changed 7 from index 10 to index 7:  0 1 2 3 5 4 6 7 8 10 9 11 15 13 14 12 16 17 18 20 19 21 22 23
20: changed 15 from index 12 to index 15:  0 1 2 3 5 4 6 7 8 10 9 11 13 14 12 15 16 17 18 20 19 21 22 23
21: changed 12 from index 14 to index 12:  0 1 2 3 5 4 6 7 8 10 9 11 12 13 14 15 16 17 18 20 19 21 22 23
22: changed 5 from index 4 to index 5:  0 1 2 3 4 5 6 7 8 10 9 11 12 13 14 15 16 17 18 20 19 21 22 23
23: changed 10 from index 9 to index 10:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 19 21 22 23
24: changed 20 from index 19 to index 20:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

It is trivial to order 24 items in 24 steps: Pick the 1st, 2nd, 3rd ... 24th.

The method explained here found 21 steps to be necessary. The greedy method seems to do quite well. However, for reversed sequences, it takes far too many swaps.

---

Update:

Here is the cycle-oriented method inspired by geeksforgeeks and a related StackOverflow post:

struct ValuePosition<T> : IComparable<ValuePosition<T>> where T : IComparable
{
    public T value;
    public int position;

    public int CompareTo(ValuePosition<T> other)
    {
        return value.CompareTo(other.value);
    }
}

static void sortWithMinimumNumberOfSwaps<T>(T[] arr) where T : IComparable
{
    int n = arr.Length;

    // Create an array of <Value, Position> pairs
    ValuePosition<T>[] arrValuePosition = new ValuePosition<T>[n];
    for (int i = 0; i < n; i++)
    {
        arrValuePosition[i].value = arr[i];
        arrValuePosition[i].position = i;
    }

    // Sort array values to get desired positions
    Array.Sort(arrValuePosition);

    // Keep track of visited elements (all initially unvisited)
    bool[] visited = new bool[n];

    //  Members of a cycle are registered here
    int[] cycle = new int[n];

    int swapCount = 0;

    // Traverse array elements
    for (int i = 0; i < n; i++)
    {
        // already swapped and corrected or
        // already present at correct pos
        if (visited[i] || arrValuePosition[i].position == i)
            continue;

        // loop trough cycle and collect comprised items
        int cycleIdx = 0;
        int j = i;
        while (!visited[j])
        {
            visited[j] = true;
            cycle[cycleIdx++] = j;

            // move to next node
            j = arrValuePosition[j].position;
        }

        //  perform resulting swaps
        while (--cycleIdx > 0)
        {
            string s = $"{++swapCount}: {arr[cycle[cycleIdx]]}[{cycle[cycleIdx]}]"
                     + $"<--> {arr[cycle[cycleIdx-1]]}[{cycle[cycleIdx-1]}]";
            T tmp = arr[cycle[cycleIdx]];

            arr[cycle[cycleIdx]] = arr[cycle[cycleIdx - 1]];
            arr[cycle[cycleIdx - 1]] = tmp;

            foreach(T t in arr)
            {
                s = s + " " + t;
            }
            Console.WriteLine(s);
        }
    }
}

Answer 2

It has been more than a year since the question was asked but I needed an answer myself and I had some time to come up with an algorithm that can produce the optimal result. I will explain it in case someone else needs it too. But you'll have to do some of the legwork yourself.

Edit: I used the Longest Increasing Subsequence algorithm from wikipedia instead of the Longest Common Subsequence. I didn't see that until later. I think my algorithm can be adapted to use the L.C.S. if you want but there may be both pros and cons.

---

To make it a little more clear why the longest increasing subsequence can result in the optimal solution, I would like to refer to this answer on another stack exchange question:

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has k values in its longest increasing subsequence, you need n−k moves at least to get it sorted. This shows n−k moves is necessary.

The problem is, like you said, that while you move items around, a lot of other items move too and the location of those items become unknown.

---

Understanding this, let's step back for a moment. You gave the following arrays:

int[] original = { 201, 203, 208, 117, 89 };
int[] desired = { 208, 117, 89, 203, 201 };

To be able to take the longest increasing subsequence and actually end up with something useful, we must number the items in such a way so that we eventually end up with one long increasing sequence:

original2 = { 4, 3, 0, 1, 2 }; // Replace every number by the index of that number in the "desired" array.
desired2 = { 0, 1, 2, 3, 4 }; // Increasing sequence / indexes.

Now it's easy to see that the L.I.S. is [0, 1, 2] and the items that must be moved are [4, 3]. Axel's answer provides us with an algorithm to get original2:

// find initial ordering
foreach(int io in original)
{
    int pos = -1;
    for (int i = 0; i < desired.Length; i++)
    {
        if (desired[i] == io)
        {
            pos = i;
            break;
        }
    }
    original2.Add(pos);
}

Let's present the array in a different way:

The ∅ represents a null item. The red (which have become purple-ish) numbers must be moved. In this case, 3 and 4 must be moved from somewhere between ∅ and 0 to somewhere between 2 and the end. Depending on the order in which items are moved, they may be inserted in a different location relative to the non-moving numbers. But we can know for certain between which non-moving numbers an item will end up at any time during the whole reordering process. Therefor, it is useful to use the non-moving numbers as anchors or beacons. These anchors can be used to determine the absolute position of an item at the time it will be removed and inserted.

To keep track of moving items relative to anchors, I will use the word "bucket". Which is just a name I gave it. Every bucket has an anchor, a list of items that have been inserted into the bucket and a list of items that will be removed from the bucket at some point.

class Bucket {
    int anchor; // The non-moving item in front of the bucket
    int[] inserted;
    int[] toBeRemoved;
}

The layout of the bucket is synonymous to the plain array. Because all items that will be removed are gone at the end of the reordering, there is no point in trying to insert new items somewhere inbetween them. There won't be any inbetween left eventually. This is only difficult when calculating the indexes. Easier is to just insert all new items before the items that will be removed.

Below this is a graphical representation of a bucket. See how each item is still in the same place as in the original2 array.

Let's move an item. It doesn't really matter in which order you move them for this algorithm. For my own usecase I want them to be moved in the same order as that they end up in. It's possible to create a list of moves that need to be performed and to sort that list or, if you don't care about the order, you could just loop through the buckets and the toBeRemoved items within them. I'm going to perform the latter one in the drawings.

To calculate the absolute index of the item we want to remove:

1. Calculate the size of every bucket before the bucket containing the item. Substract one to exclude the null-item in the first bucket.

   numBeforeBucket = buckets.TakeWhile(b => b != sourceBucket)
                            .Sum(b => 1 + b.inserted.Length + b.toBeRemoved.Length) - 1
   

2. Calculate the number of items before the current item within the current bucket.

   numBeforeInBucket = 1 + sourceBucket.inserted.Length + indexOfItemWithinTheToBeRemovedArray
   

3. Sum those values together.

   sourceIndex = numBeforeBucket + numBeforeInBucket
   

Now remove the item from the bucket:

// You probably know the value already from one of the loop variables,
// but if you don't:
var item = sourceBucket.toBeRemoved[indexOfItemWithinTheToBeRemovedArray];
sourceBucket.toBeRemoved.Remove(item);

Note: if the slide.MoveTo(int toPos) method in PowerPoint takes a target position as if the item hasn't been removed yet, you need to wait with removing the item from the bucket until you have calculated the target position as well.

To calculate the absolute index where to insert the item:

1. Calculate the size of every bucket before the bucket the item will be inserted into. Substract one to exclude the null-item in the first bucket.

   numBeforeBucket = buckets.TakeWhile(b => b != targetBucket)
                            .Sum(b => 1 + b.inserted.Length + b.toBeRemoved.Length) - 1
   

2. Calculate the number of items before the new item within the destination bucket.

   // Determine where to insert the item. Everything in "inserted" is
   // already sorted so just get the index of the first item with a
   // larger value. The way that .Insert(index, value) works is that
   // the item will be inserted before the item currently occupying
   // that index, pushing the occupying item to the right.
   var i = 0;
   for(; i < targetBucket.inserted.Length; i++) {
       var current = targetBucket.inserted[i];
       if(current > item) { // Item is the same variable from when we removed it.
           break;
       }
   }
   var indexOfItemWithinInsertedArray = i; // For clarity.
   
   numBeforeInBucket = 1 + indexOfItemWithinInsertedArray
   

3. Sum the values together and substract one.

   targetIndex = numBeforeBucket + numBeforeInBucket
   

Insert the item into the bucket:

targetBucket.inserted.Insert(indexOfItemWithinInsertedArray, item);

Now repeat for all items that must be moved.

I tried to use valid C#. I haven't done C# in a while though and my proof of concept was written in Go which does looping and array manipulation just a little different. You may need to change some .Length for some .Count(). If things don't work, I suggest looking for an off-by-one error.

If you need more explaining or exampling, just ask.