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
Post a Comment