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

Question

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

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

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

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

环顾互联网，我得出的结论是找到 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，我只能通过 slide.MoveTo(int toPos) 来排序。（除此之外，我可以随时通过索引找到幻灯片的 ID，反之亦然。）

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

谁能帮我生成一个 (int sourceIndex, int targetIndex) 或 (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 and a related Whosebug 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

问这个问题已经一年多了，但我自己需要一个答案，我有一些时间想出一个可以产生最佳结果的算法。我会解释它以防其他人也需要它。但是你必须自己做一些跑腿工作。

编辑：我使用了 Longest Increasing Subsequence algorithm from wikipedia 而不是最长的 Common 子序列。直到后来我才看到。我想我的算法可以适应使用L.C.S。如果你愿意，但可能有利有弊。

为了更清楚为什么最长递增子序列可以得到最优解，我想参考this answer另一个堆栈交换问题：

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.

问题是，正如您所说，当您四处移动物品时，许多其他物品也会移动，并且这些物品的位置变得未知。

了解了这一点，让我们退后一步。您提供了以下数组：

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

为了能够采用最长的递增子序列并最终得到有用的东西，我们必须以这样一种方式对项目进行编号，以便我们最终得到一个长的递增序列：

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.

现在很容易看出 L.I.S。是 [0, 1, 2]，必须移动的项目是 [4, 3]。 Axel 的回答为我们提供了一个算法来得到 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);
}

让我们以不同的方式展示数组：

这个∅代表一个null item。必须移动红色（已变成紫色）数字。在这种情况下，3 和 4 必须从 ∅ 和 0 之间的某处移动到 2 和末尾之间的某处。根据项目移动的顺序，它们可能被插入到相对于非移动数字的不同位置。但是我们可以确定在整个重新排序过程中的任何时候，一个项目将在哪些非移动数字之间结束。因此，使用非移动数字作为锚点或信标很有用。这些锚点可用于确定项目在删除和插入时的绝对位置。

为了跟踪相对于锚点的移动项目，我将使用“桶”这个词。这只是我给它起的名字。每个桶都有一个锚点、一个已插入桶中的项目列表和一个将在某个时候从桶中删除的项目列表。

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

桶的布局与普通数组同义。因为所有将被删除的项目在重新排序结束时都消失了，所以尝试在它们之间的某个地方插入新项目是没有意义的。最终不会有任何中间人离开。这仅在计算索引时比较困难。更简单的方法是在将要删除的项目之前插入所有新项目。

下面是一个桶的图形表示。查看每个项目如何仍位于 original2 数组中的相同位置。

让我们移动一个项目。对于此算法，您以何种顺序移动它们并不重要。对于我自己的用例，我希望它们按照它们最终出现的顺序移动。可以创建需要执行的移动列表并对该列表进行排序，或者，如果您不关心顺序，您可以循环遍历存储桶和其中的 toBeRemoved 项。我要在图纸中表演后一个。

要计算我们要删除的项目的绝对索引：

计算包含该项目的桶之前的每个桶的大小。减去一个以排除第一个桶中的空项。

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

计算在当前桶中当前项目之前的项目数。

numBeforeInBucket = 1 + sourceBucket.inserted.Length + indexOfItemWithinTheToBeRemovedArray

将这些值相加。

sourceIndex = numBeforeBucket + numBeforeInBucket

现在从存储桶中删除项目：

// 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);

注意：如果 PowerPoint 中的 slide.MoveTo(int toPos) 方法采用目标位置，就好像项目尚未被删除一样，您需要等待从存储桶中删除项目，直到计算出目标位置还有。

计算插入项目的绝对索引：

计算项目将被插入的桶之前的每个桶的大小。减去一个以排除第一个桶中的空项。

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

计算目标桶中新项目之前的项目数。

// 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

将值相加并减一。

targetIndex = numBeforeBucket + numBeforeInBucket

将项目插入桶中：

targetBucket.inserted.Insert(indexOfItemWithinInsertedArray, item);

现在对所有必须移动的项目重复此操作。

我尝试使用有效的 C#。不过我已经有一段时间没有使用 C# 了，我的概念证明是用 Go 编写的，它的循环和数组操作略有不同。您可能需要为某些 .Count() 更改一些 .Length。如果事情不起作用，我建议寻找一个差一错误。

如果您需要更多解释或示例，请询问。

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

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

c#

arrays

algorithm

subsequence