arrays - How to find a list of steps needed to reorder a list to get another list? -


let's assume have lists (expressed arrays or whatever in language). these lists equally long , contain same unique elements - in different order.

for example:

first list: a, b, c, d second list: a, d, b, c 

now i'm trying find list of steps needed reorder first list match second list. in example, there 1 step:

3 -> 1 

that is, because element @ index 3 moved index 1. note b , c change indexes, because "making space" d when inserted @ index 1, step should not included in list of moves!

another example:

first list: a, b, c, d, e, f second list: d, b, a, c, e, f changes:  3 -> 0, 1 -> 1 

because d moved index 0 , b moved 1. note b, use original index 1 instead of have been after first move performed.

these steps "performed @ once" - meaning there no order, create new list putting moved elements should , filling remaining slots remaining elements.

now question is: know algorithm this?

thanks in advance! :)

if need shortest list of steps, perform longest increasing subsequence on list , change position of elements outside subsequence.


Comments

Popular posts from this blog

php - failed to open stream: HTTP request failed! HTTP/1.0 400 Bad Request -

java - How to filter a backspace keyboard input -

java - Show Soft Keyboard when EditText Appears -