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?
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);
}
}
}