算法要"synchronize"（副作用）一个列表跟另一个？ （不使用掉期）
Algorithm to "synchronize" (side effect) a list with another? (Without using swaps)
我正在尝试编写一种在某些限制条件下将列表与另一个列表同步的方法，但到目前为止我还没有想出合适的算法来做到这一点。
以下是所有详细信息：
- 方法调用后，目标列表将与源列表完全相同的元素，顺序相同
- 目标列表中的某些元素可以删除，其他元素可以添加，其他元素可以不同位置
- 我无法对目标列表进行排序，也无法使用 交换操作（因为 UI 显示给用户，我不想要 UI闪烁)
编辑：添加一些细节，列表是一个 ObservableCollection 对象，我不想只将第二个列表分配给第一个列表这将使整个 ListView 控件（UWP 应用程序）刷新内容。相反，我希望 "right" 项保留在原处，并且我希望其他项很好地 added/removed 在正确的位置。此外，在可能的情况下，错误位置的项目应该 "slide" 在正确的位置，例如，如果我要删除的项目位于其正确最终位置之前一个位置的项目之前。
结果我只能对目标列表进行如下操作：
- 在给定索引
处插入一个项目
- 从给定索引
中删除一个项目
我需要算法对目标列表执行尽可能少的操作。
示例:
target = { "tree", "house", "beach" }
source = { "tree", "beach", "house", "peach" }
在这种情况下，我会从第一个列表中删除 "house" 项，这样 "beach" 就会在正确的位置滑动，然后再次添加 "house"（在右侧位置），最后 "peach" 在列表的末尾。
这是我想到的一般原型：
/// <summary>
/// Synchronizes a list with the items in the second list
/// </summary>
/// <typeparam name="T">The type of the items in the lists</typeparam>
/// <param name="target">The target list to edit</param>
/// <param name="source">The source list (ordered)</param>
/// <param name="comparer">A comparer function to check if two items are the same, and if a list contains a given item (by using the Any LINQ)</param>
/// <param name="indexer">An action used to assign the right final index to an element in the target list</param>
public static void Synchronize<T>([NotNull] IList<T> target, [NotNull] IReadOnlyList<T> source,
[NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
// Edge case
if (target.Count == 0)
{
foreach (T item in source)
target.Add(item);
return;
}
if (target.Count < source.Count)
{
/* At least a new item has been added, but there's
* no guarantee it'll be at the end of the source list */
}
else if (target.Count > source.Count)
{
/* One or more items have been removed from the target list,
* but at the same time the source list could have one or more new items
* that weren't present in the target list before */
}
else
{
/* The two lists have the same length, but I can make no assumptions
* on their content. Every item could be different, or they could have the same
* items but in different positions, or some items right, some in the wrong
* positions and some new items as well */
}
}
注意：每个列表不会超过20个项目，所以我不关心算法成本，它可能是O(n^2)并且它' d 仍然很好。
注意#2：需要indexer函数，因为在同步结束时，目标列表中的每个项目都必须知道它在列表，所以我可以对所有最终处于不同位置的项目（以及所有新项目）使用该操作，让他们知道他们的最终位置。
我需要有关伪代码的帮助，我并没有开始编写代码，因为我想首先为该问题想出一个像样的算法，我已经考虑了一段时间，但我'我不确定我是否知道解决此问题的正确方法。
感谢您的帮助！
解决方案：这是我写的最终实现（经过测试，效果很好）
/// <summary>
/// Synchronizes a list with the items in the second list
/// </summary>
/// <typeparam name="T">The type of the items in the lists</typeparam>
/// <param name="target">The target list to edit</param>
/// <param name="source">The source list (ordered)</param>
/// <param name="comparer">A comparer function to check if two items are the same, and if a list contains a given item (by using the Any LINQ)</param>
/// <param name="indexer">An action used to assign the right final index to an element in the target list</param>
public static void Synchronize<T>([NotNull] this IList<T> target, [NotNull] IReadOnlyList<T> source,
[NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
// Edge case
if (target.Count == 0)
{
foreach (T item in source)
target.Add(item);
return;
}
// Step 1
for (int i = 0; i < target.Count; i++)
{
// Remove all the items in target that are not in source
if (!source.Any(item => comparer(item, target[i])))
{
target.RemoveAt(i--);
}
}
// Step 2
List<T> copy = source.Where(item => target.Any(test => comparer(test, item))).ToList();
List<(T, int, int)> lookup = new List<(T, int, int)>();
for (int i = 0; i < target.Count; i++)
{
// Check if the item is out of place
T current = target[i];
if (!comparer(current, copy[i]))
{
// Store the item and its target index in the lookup table
int index = copy.IndexOf(item => comparer(item, current));
lookup.Add((current, i, index));
}
}
// Adjust the items in the wrong positions
lookup.Sort(tuple => -(tuple.Item3 - tuple.Item2).Abs());
while (lookup.Count > 0)
{
// Move the items in the right position
(T item, int current, int desired) = lookup.First();
lookup.RemoveAt(0);
// Adjust the current index if the element has shifted
if (!comparer(target[current], item))
{
current = target.IndexOf(pick => comparer(pick, item));
}
// Skip if the element has already been shifted into its right place
if (current == desired) continue;
// Adjust the current item
target.RemoveAt(current);
target.Insert(desired, item);
}
// Step 3
for (int i = 0; i < source.Count; i++)
{
// Insert the missing elements
if (!target.Any(item => comparer(item, source[i])))
{
target.Insert(i, source[i]);
}
}
// Adjust the indexes
for (int i = 0; i < target.Count; i++)
{
indexer(target[i], i);
}
}
第 1 步：遍历目标列表，并删除不在源列表中的任何元素。
第 2 步：再次遍历目标列表，注意每个元素与其正确位置的距离（不包括丢失的元素）。删除最不合适的元素，并将其插入正确的位置。重复直到元素的顺序正确。
第 3 步：遍历两个列表，插入缺少的元素。
我认为这是最小的。
你最终得到的算法对我来说似乎太复杂了。由于您可以接受 O(N^2) 时间复杂度，因此以下简单算法应该可以完成这项工作：
对于源列表中的每个位置，检查目标项目是否存在于该位置，以及它是否与该位置的源项目相同，即目标项目是否在其最终位置。如果是，什么也不做。否则，搜索目标的其余部分（请记住，每一步都确保目标项目位于其最终位置，因此它不能在当前位置之前）在该位置寻找源项目的相应项目，如果找到，则将其删除.然后只需将源项目插入目标中的那个位置。
完成上述遍后，移除位置>= source.Count的目标项目。
仅此而已。不需要边缘情况，因为它可以顺利处理它们。
public static void Synchronize<T>([NotNull] IList<T> target, [NotNull] IReadOnlyList<T> source,
[NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
for (int pos = 0; pos < source.Count; pos++)
{
if (pos >= target.Count || !comparer(target[pos], source[pos]))
{
// Either no target item at that position or the target item at that position
// is different from the source item at that position.
// Remove the corresponding target item (if any) from its original position.
for (int i = pos + 1; i < target.Count; i++)
{
if (comparer(target[i], source[pos]))
{
target.RemoveAt(i);
break;
}
}
// Insert the source item at that position
target.Insert(pos, source[pos]);
}
// The target item is in its final position
indexer(target[pos], pos);
}
// Remove the remaining target items if any
for (int i = target.Count - 1; i >= source.Count; i--)
target.RemoveAt(i);
}
我正在尝试编写一种在某些限制条件下将列表与另一个列表同步的方法，但到目前为止我还没有想出合适的算法来做到这一点。
以下是所有详细信息：
- 方法调用后，目标列表将与源列表完全相同的元素，顺序相同
- 目标列表中的某些元素可以删除，其他元素可以添加，其他元素可以不同位置
- 我无法对目标列表进行排序，也无法使用 交换操作（因为 UI 显示给用户，我不想要 UI闪烁)
编辑：添加一些细节，列表是一个 ObservableCollection 对象，我不想只将第二个列表分配给第一个列表这将使整个 ListView 控件（UWP 应用程序）刷新内容。相反，我希望 "right" 项保留在原处，并且我希望其他项很好地 added/removed 在正确的位置。此外，在可能的情况下，错误位置的项目应该 "slide" 在正确的位置，例如，如果我要删除的项目位于其正确最终位置之前一个位置的项目之前。
结果我只能对目标列表进行如下操作：
- 在给定索引 处插入一个项目
- 从给定索引 中删除一个项目
我需要算法对目标列表执行尽可能少的操作。
示例:
target = { "tree", "house", "beach" }
source = { "tree", "beach", "house", "peach" }
在这种情况下，我会从第一个列表中删除 "house" 项，这样 "beach" 就会在正确的位置滑动，然后再次添加 "house"（在右侧位置），最后 "peach" 在列表的末尾。
这是我想到的一般原型：
/// <summary>
/// Synchronizes a list with the items in the second list
/// </summary>
/// <typeparam name="T">The type of the items in the lists</typeparam>
/// <param name="target">The target list to edit</param>
/// <param name="source">The source list (ordered)</param>
/// <param name="comparer">A comparer function to check if two items are the same, and if a list contains a given item (by using the Any LINQ)</param>
/// <param name="indexer">An action used to assign the right final index to an element in the target list</param>
public static void Synchronize<T>([NotNull] IList<T> target, [NotNull] IReadOnlyList<T> source,
[NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
// Edge case
if (target.Count == 0)
{
foreach (T item in source)
target.Add(item);
return;
}
if (target.Count < source.Count)
{
/* At least a new item has been added, but there's
* no guarantee it'll be at the end of the source list */
}
else if (target.Count > source.Count)
{
/* One or more items have been removed from the target list,
* but at the same time the source list could have one or more new items
* that weren't present in the target list before */
}
else
{
/* The two lists have the same length, but I can make no assumptions
* on their content. Every item could be different, or they could have the same
* items but in different positions, or some items right, some in the wrong
* positions and some new items as well */
}
}
注意：每个列表不会超过20个项目，所以我不关心算法成本，它可能是O(n^2)并且它' d 仍然很好。
注意#2：需要indexer函数，因为在同步结束时，目标列表中的每个项目都必须知道它在列表，所以我可以对所有最终处于不同位置的项目（以及所有新项目）使用该操作，让他们知道他们的最终位置。
我需要有关伪代码的帮助，我并没有开始编写代码，因为我想首先为该问题想出一个像样的算法，我已经考虑了一段时间，但我'我不确定我是否知道解决此问题的正确方法。
感谢您的帮助！
解决方案：这是我写的最终实现（经过测试，效果很好）
/// <summary>
/// Synchronizes a list with the items in the second list
/// </summary>
/// <typeparam name="T">The type of the items in the lists</typeparam>
/// <param name="target">The target list to edit</param>
/// <param name="source">The source list (ordered)</param>
/// <param name="comparer">A comparer function to check if two items are the same, and if a list contains a given item (by using the Any LINQ)</param>
/// <param name="indexer">An action used to assign the right final index to an element in the target list</param>
public static void Synchronize<T>([NotNull] this IList<T> target, [NotNull] IReadOnlyList<T> source,
[NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
// Edge case
if (target.Count == 0)
{
foreach (T item in source)
target.Add(item);
return;
}
// Step 1
for (int i = 0; i < target.Count; i++)
{
// Remove all the items in target that are not in source
if (!source.Any(item => comparer(item, target[i])))
{
target.RemoveAt(i--);
}
}
// Step 2
List<T> copy = source.Where(item => target.Any(test => comparer(test, item))).ToList();
List<(T, int, int)> lookup = new List<(T, int, int)>();
for (int i = 0; i < target.Count; i++)
{
// Check if the item is out of place
T current = target[i];
if (!comparer(current, copy[i]))
{
// Store the item and its target index in the lookup table
int index = copy.IndexOf(item => comparer(item, current));
lookup.Add((current, i, index));
}
}
// Adjust the items in the wrong positions
lookup.Sort(tuple => -(tuple.Item3 - tuple.Item2).Abs());
while (lookup.Count > 0)
{
// Move the items in the right position
(T item, int current, int desired) = lookup.First();
lookup.RemoveAt(0);
// Adjust the current index if the element has shifted
if (!comparer(target[current], item))
{
current = target.IndexOf(pick => comparer(pick, item));
}
// Skip if the element has already been shifted into its right place
if (current == desired) continue;
// Adjust the current item
target.RemoveAt(current);
target.Insert(desired, item);
}
// Step 3
for (int i = 0; i < source.Count; i++)
{
// Insert the missing elements
if (!target.Any(item => comparer(item, source[i])))
{
target.Insert(i, source[i]);
}
}
// Adjust the indexes
for (int i = 0; i < target.Count; i++)
{
indexer(target[i], i);
}
}
第 1 步：遍历目标列表，并删除不在源列表中的任何元素。
第 2 步：再次遍历目标列表，注意每个元素与其正确位置的距离（不包括丢失的元素）。删除最不合适的元素，并将其插入正确的位置。重复直到元素的顺序正确。
第 3 步：遍历两个列表，插入缺少的元素。
我认为这是最小的。
你最终得到的算法对我来说似乎太复杂了。由于您可以接受 O(N^2) 时间复杂度，因此以下简单算法应该可以完成这项工作：
对于源列表中的每个位置，检查目标项目是否存在于该位置，以及它是否与该位置的源项目相同，即目标项目是否在其最终位置。如果是，什么也不做。否则，搜索目标的其余部分（请记住，每一步都确保目标项目位于其最终位置，因此它不能在当前位置之前）在该位置寻找源项目的相应项目，如果找到，则将其删除.然后只需将源项目插入目标中的那个位置。
完成上述遍后，移除位置>= source.Count的目标项目。
仅此而已。不需要边缘情况，因为它可以顺利处理它们。
public static void Synchronize<T>([NotNull] IList<T> target, [NotNull] IReadOnlyList<T> source,
[NotNull] Func<T, T, bool> comparer, [NotNull] Action<T, int> indexer)
{
for (int pos = 0; pos < source.Count; pos++)
{
if (pos >= target.Count || !comparer(target[pos], source[pos]))
{
// Either no target item at that position or the target item at that position
// is different from the source item at that position.
// Remove the corresponding target item (if any) from its original position.
for (int i = pos + 1; i < target.Count; i++)
{
if (comparer(target[i], source[pos]))
{
target.RemoveAt(i);
break;
}
}
// Insert the source item at that position
target.Insert(pos, source[pos]);
}
// The target item is in its final position
indexer(target[pos], pos);
}
// Remove the remaining target items if any
for (int i = target.Count - 1; i >= source.Count; i--)
target.RemoveAt(i);
}