I'm making an app where shuffling arrays are one of the main components. It's not really relevant what the arrays contain, but for simplicity I've used single characters in my example code below. The array will in most cases contain 1-3000 elements, but possibly more.
Array a represents the original state of the array, and array b is the final state I want the array to be in. The state of b can be made using any number of transformations, but after shuffling I want to find the minimal set of transformations that needs to be done in order to transform array a into the same state as array b.
There are some limitations to what transformations that can be done however. I'll be using an API for shuffling the array, which is why I want to find the smallest (or close to) number of transformations required, to minimize the number of requests.
Transformations can only be done by picking a start index of the element(s) you want to move, a range of how many consecutive elements you want to move at a time, and which index you want to place the range before. The list of transformations can be ordered so that each transformation uses the previous result, or they can all use the original state of a as a base.
Some example pseudo-javascript code:
const a = ['a', 'b', 'c', 'd', 'e']
const b = ['d', 'c', 'a', 'b', 'e']
const getTransformations = (a, b) => {
// ...
return [
{start: 0, range: 2, before: 4},
{start: 0, range: 1, before: 2}
]
}
Because I will be using different shuffling algorithms, I would prefer to be using the original and the final state of the array to calculate the transformations, but if there are other solutions that are more effective that requires slightly different input that could work as well.
What I'm really interested in is to know if this is a problem that can be solved in a reasonably amount of time, and if there are any algorithms that can help me do this.
