Changing the list from order A to order B using only push and remove operations

Question

Is there any known algorithm (or obvious solution) for converting a list from order A to order B using only push and remove operations? For example, from abcd to bcad you can perform the following operations:

 remove(a) remove(d) push(a) push(d) 

Or, from cba to ab will be

 remove(c) remove(b) push(b) 

Or from acb to acbd will be

 push(d) 

Here, push adds an element to the end of the list, and remove removes the element and shifts subsequent elements so that the list is always in a continuous state (without "empty slots"). In addition, there is a condition that at any time the list may contain the same element only once. Therefore, it seems that first you need to do everything remove in one bundle, and after that all push es. The order of remove is obviously irrelevant, but the order of push es.

A trivial solution would be to remove all the elements first, and then click the desired elements in the desired order. But since I know that most conversions will be quite small, which is equivalent to a single push es or remove s, I want to "reuse" any existing correct order in the list (for example, converting abcdef to abcde will require only one remove operation - this is a great alternative (6 + 5 operations)). So how to choose the correct (minimal) remove set and push es list?

Answer 1

From what I can say, you are going to remove from anywhere and click on the back.

Since you cannot insert in the middle of the list, the only way to minimize the number of operations is to go through the list linearly and remove any item that is not correct.

i.e. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 2, 4, 6, 7, 8, 13, 14

• compare 1
  • delete 1
• compare 2
• compare 3
  • remove 3
• compare 4
• compare 5
  • remove 5
• compare 6
• compare 7
• compare 8
• compare 9
  • remove 9
• compare 10
  • delete 10 (completion reached)
• push 13
• push 14

If your push was not so limited, there would be more effective ways to do it.

Answer 2

This is not “well known,” but rather something that I just came up with.

• Remove all elements of the original that are not in the desired list; add each delete operation to the list of operations.
• Add any items for work that are missing; add each add operation to the list of operations.
• Assign each element of the source list a "serial number", which is the position of its counterpart in the desired list. (see snippet below.)
• Find the first element (0 in the original 1 ) and the last element in order from there (1 in the original 2 ).
• Remove all elements at positions outside this range and put them in some other temporary list; add each delete operation to the list of operations.
• Sort temporary list based on "order number".
• Add items in order from the temporary list; add each add operation to the list of operations.
• Make sure this newly converted list matches the list.
• Returns a list of operations.

Ex. from step 2:

2013 1234

abcd bcad

Since you can add and remove only those elements that are not added or not added / deleted, I do not think that you can keep the existing order of any sub-segments in a different order than the segment in order 0. That's why all the other elements are deleted in step 4 Since you do not need to add these elements immediately after deletion (based on your example), I assume that it is normal to store them somewhere. So, why not save them in a sorted list and sort them based on the assigned “order number” to determine the order of additions?

If I do not understand your question, you are interested in the order of the operations of adding / removing, so you do not need to actually convert the list (since you already have the converted list); you need steps to create a converted list. Therefore, every time you add or remove in the algorithm, add the "operation" to the list (queue) of operations (for example, operations.Add("remove(a)") ). The algorithm then returns this list of operations.

I wrote a possible implementation in C #. I checked it a bit (screenshots below) and it seemed to work. However, this may not be the best implementation that someone could write.

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

Answer 3

Cerebral:

• Arbitrary ordering can be thought of as sorting, given the correct comparison function.
• A Cartesian tree has the interesting property that it models both the original list order (by traversing the space) and the sorted list order (in the form of a heap).

Perhaps you can use the Cartesian tree to determine the order of operations as follows (edited to correct errors detected when working in the example below):

• Call source list L.
• Build a Cartesian tree T from L. This takes O (n) time.
• Build an empty priority queue Q.
• Assign node N = root of T (this is the smallest element in the list that has not yet been processed).
• Repeat the following steps until Q is empty and N is null.
  • Remove all left children from N from L and place them in Q. Element N is now in position on L.
  • Assign N = right child of N.
  • If N <chapter Q: remove N from L and put it on Q.
  • While the head is Q <= N or N == null: pop Q and press the result on L.

Let's try an example:

I will use the example from the Wikipedia page of Cartesian trees :

At the beginning:

• L = 9,3,7,1,8,12,10,20,15,18,5
• Q = empty
• N = 1

First cycle:

• Move left children from N to Q:
  • L = 1,8,12,10,20,15,5
  • Q = 3,7,9
• Move N to the right child: N = 5
• Move N to Q
  • L = 1,8,12,10,20,15
  • Q = 3,5,7,9
• Press points <= N from Q to L:
  • L = 1,8,12,10,20,15,3,5
  • Q = 7.9

Second cycle:

• Move left children from N to Q:
  • L = 1,3,5
  • Q = 7.8,9,10,12,15,20
• Move N to the right child: N = null
• Press the remaining items from Q to L:
  • L = 1,3,5,7,8,9,10,12,15,20

Done.