This isn't "well known", but rather something I just thought up.
Remove all elements from the original that are not in the desired list; add each remove operation to the list of operations.Add any elements to working that are missing; add each add operation to the list of operations.- Assign to each element of the original list a "order number" which is the position of its analog in the desired list. (see snippet below.)
- Find the first element (0 at original1) and the last element in order from there (1 at original2).
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.- Sort the temporary list based on the "order number".
Add the elements in order from the temporary list; add each add operation to the list of operations.- Verify that this newly transformed list matches the desired list.
- Return the list of operations.
Ex. from step 2:
2013 1234
abcd bcad
Because you can only add and remove--not insert elements or add/remove a range--I don't think you can keep the existing order of any in-order sub-segments other than the in-order segment from 0. That's why all other elements are removed in step 4. Since you don't have to add those elements immediately after removing (based on your example), I assume it's ok to store them somewhere. So, why not store them in a sortable list and sort based on the assigned "order number" to determine the order of adds?
Unless I've misunderstood your question, you're interested in the order of add/remove operations, so you don't care about actually transforming the list (since you already have the transformed list); you want the steps to create the transformed list. Therefore, each time you add or remove in the algorithm, add the "operation" into a list (queue) of operations (e.g. operations.Add("remove(a)")). The algorithm then returns this list of operations.
I wrote a possible implementation in C#. I tested it a little (screen shots below) and it seemed to work. It might also not be the best implementation that someone could write, however.
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;
}
