Это не "хорошо известно", а то, что я только что придумал.
Remove все элементы из оригинала, которых нет в нужном списке; добавьте каждую операцию удаления в список операций. Add любые элементы для работы, которые отсутствуют; добавьте каждую операцию добавления в список операций. - Назначьте каждому элементу исходного списка «номер заказа», который является позицией его аналога в требуемом списке. (см. фрагмент ниже.)
- Найдите первый элемент (0 в исходном 1 ) и последний элемент в том порядке (1 в исходном 2 ).
Remove все элементы на позициях за пределами этого диапазона и помещать их в какой-то другой временный список; добавьте каждую операцию удаления в список операций. - Сортировка временного списка по «номеру заказа».
Add элементы в порядке из временного списка; добавьте каждую операцию добавления в список операций. - Убедитесь, что этот вновь преобразованный список соответствует требуемому списку.
- Вернуть список операций.
Ex. из шага 2:
2013 1234
abcd bcad
Поскольку вы можете только добавлять и удалять, а не вставлять элементы или добавлять / удалять диапазон, я не думаю, что вы можете сохранить существующий порядок любых подсегментов в порядке , кроме сегмент по порядку от 0. Вот почему все остальные элементы удаляются на шаге 4. Поскольку вам не нужно добавлять эти элементы сразу после удаления (на основе вашего примера), я предполагаю, что их можно где-то хранить. Итак, почему бы не сохранить их в сортируемом списке и отсортировать по назначенному «порядковому номеру» для определения порядка добавления?
Если я не понял ваш вопрос, вас интересует порядок операций добавления / удаления, поэтому вам не нужно фактически преобразовывать список (поскольку у вас уже есть преобразованный список); Вы хотите шаги, чтобы создать преобразованный список. Поэтому каждый раз, когда вы добавляете или удаляете в алгоритме, добавляйте «операцию» в список (очередь) операций (например, operations.Add("remove(a)")). Затем алгоритм возвращает этот список операций.
Я написал возможную реализацию в C #. Я немного проверил (скриншоты ниже), и, похоже, это сработало. Однако это может быть и не самая лучшая реализация, которую кто-то может написать.
public static IEnumerable<string> DetermineTransformOrder<T>(
IEnumerable<T> original, IEnumerable<T> desired)
{
// handle the easy case immediately
if (original.SequenceEqual(desired))
{
return new List<string>();
}
List<KeyValuePair<int,T>> workingOriginal = new List<KeyValuePair<int,T>>();
List<T> workingDesired = desired.ToList();
List<string> operations = new List<string>(); //using Queue<> is ok too
// load workingOriginal
foreach(T element in original)
workingOriginal.Add(new KeyValuePair<int, T>(workingDesired.IndexOf(element), element));
//1. Remove all elements from the original that are not in the desired list;
// add each remove operation to the list of operations.
var tempWorking = new List<KeyValuePair<int,T>>(workingOriginal);
foreach (var element in tempWorking)
{
if (!workingDesired.Contains(element.Value))
{
workingOriginal.Remove(element);
operations.Add("remove(" + element.Value.ToString() + ")");
}
}
//2. Add any elements to working that are missing;
// add each add operation to the list of operations.
tempWorking = new List<KeyValuePair<int,T>>(workingOriginal);
foreach(T element in workingDesired)
{
if(!workingOriginal.Exists(x=>x.Value.Equals(element)))
{
workingOriginal.Add(new KeyValuePair<int, T>(workingDesired.IndexOf(element), element));
operations.Add("add("+element+")");
}
}
//3. Assign to each element of the original list a "order number"
// which is the position of its analog in the desired list.
// note: already done above. would have done it here, but
// KeyValuePair.Key is read-only.
//4. Find the first element (0 at original[1]) and the
// last element in order from there (1 at original[2]).
int indexOfFirstElement = workingOriginal.FindIndex(x => x.Key == 0);
int indexOfLastElement = indexOfFirstElement;
// move to index of last in-order element
for (int i = indexOfLastElement + 1;
i < workingOriginal.Count &&
workingOriginal[i - 1].Key + 1 == workingOriginal[i].Key;
i++, indexOfLastElement++) ;
//5. Remove all elements at positions outside of this range and put them in some
// other temporary list; add each remove operation to the list of operations.
List<KeyValuePair<int, T>> temporary = new List<KeyValuePair<int, T>>();
var inOrderElements = workingOriginal.GetRange(
indexOfFirstElement,
indexOfLastElement - indexOfFirstElement + 1);
var outOfOrderElements = new List<KeyValuePair<int, T>>(
workingOriginal.Except(inOrderElements));
foreach (var element in outOfOrderElements)
{
workingOriginal.Remove(element);
temporary.Add(element);
operations.Add("remove(" + element.Value.ToString() + ")");
}
//6. Sort the temporary list based on the "order number".
temporary.Sort((x, y) => { return x.Key.CompareTo(y.Key); });
//7. Add the elements in order from the temporary list;
// add each add operation to the list of operations.
foreach (var element in temporary)
{
workingOriginal.Add(element);
operations.Add("add(" + element.Value.ToString() + ")");
}
//8. Verify that this newly transformed list matches the desired list.
var newlyTransformed = workingOriginal.ConvertAll<T>(x => { return x.Value; });
if (!newlyTransformed.SequenceEqual(desired))
{
// this should never happen
throw new StackOverflowException("FAILED");
}
//9. Return the list of operations.
return operations;
}
