c# - 在 C# 中以最少的步骤重新排序元素集合

Question

我有一个元素列表(即 PowerPoint 幻灯片)，我需要以尽可能少的步骤重新排序。

每张幻灯片都有一个整数唯一键(即 SlideID )，我可以非常快地生成所需的键顺序，但实际上移动幻灯片(执行移动)相对较慢，因为 PowerPoint 更新谁知道-什么时候调用它，因此我尝试执行最少量的移动命令。

所以我所拥有的是原始和所需顺序的键列表，例如:

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

环顾互联网，我得出的结论是找到 Longest Common Subsequence并将其他所有内容移动到所需位置即可满足我的需要，因此我实现了 T[] FindLCS<T>(T[] first, T[] second)从Rosetta Code中借用和改编代码的方法.

为了重新排序幻灯片，我获得了非常有限的 API，我只能通过 slide.MoveTo(int toPos) 进行排序。 . (除此之外，我可以随时通过索引找到幻灯片的 ID，反之亦然。)

我在实现剩余部分时遇到了麻烦，即生成我可以执行的实际移动列表，因为移动幻灯片 x 会在其间移动所有幻灯片索引，我对如何解释这一点感到困惑。

谁能帮我制作一份 (int sourceIndex, int targetIndex) 的 list ？或 (int id, int targetIndex)我可以简单地迭代元组吗？

Answer 1

这里有一个贪心算法，它根据与所需位置的距离选择要移动的元素:

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

一旦所有项目都正确放置，算法就会停止。

---

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

这是一个包含 24 个项目的示例:

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 个项目是微不足道的:选择第 1、2、3 ... 24。

方法解释here发现需要 21 个步骤。贪婪的方法似乎做得很好。然而，对于反向序列，它需要太多的交换。

---

更新:

这是受 geeksforgeeks 启发的面向循环的方法和相关的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);
        }
    }
}