在C＃中以最少的步骤对元素集合进行重新排序 [英] Reorder a collection of elements in minimum number of steps in C#
问题描述
我有一个元素列表（即PowerPoint幻灯片），需要以尽可能少的步骤对其进行重新排序。
I have a list of elements (namely PowerPoint slides) which I need to reorder in the minimal possible steps.
每张幻灯片都有一个整数唯一键（即 SlideID ），我可以非常快速地生成所需的键顺序，但是实际上移动幻灯片（执行移动）相对较慢，因为PowerPoint更新了who-knows-whats它被调用，因此我尝试执行最少数量的移动命令。
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 };
环顾互联网，我得出的结论是找到最长的公共子序列，然后将其他所有内容移到所需位置即可，因此我实现了 T [] FindLCS ; T>（T []第一个，T []第二个）方法从罗塞塔代码。
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.
对于幻灯片的重新排序，我提供了非常有限的API，我只能按幻灯片进行订购.MoveTo（int toPos）。 （除此之外，我可以随时通过它的索引找到索引的编号，反之亦然。）
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.)
我很难实现其余部分，即生成实际列表我可以执行的移动次数，因为移动幻灯片x会在所有幻灯片索引之间移动，因此我对如何解释这一点感到困惑。
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.
有人可以帮我生成一个（int sourceIndex，int targetIndex）或（int id，int targetIndex）元组的列表我可以简单地进行迭代吗？
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.
下面是一个包含24个项目的示例：
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
以24个步骤订购24个项目很简单：选择1st，2nd，3rd。 .. 24日。
It is trivial to order 24 items in 24 steps: Pick the 1st, 2nd, 3rd ... 24th.
该方法说明了此处找到了21个必要步骤。贪婪的方法似乎做得很好。但是，对于反向序列，它需要进行太多的交换。
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.
更新：
此处是受 geeksforgeeks 和相关的 StackOverflow帖子：
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);
}
}
}
这篇关于在C＃中以最少的步骤对元素集合进行重新排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
