diff 2 arrays where items were simply reordered

Question

Given two arrays arr1 and arr2 that both have the same items, but are sorted differently, how to make a list of least number of item-move operations required to make arr1 match arr2?

The function / algorithm to do this should accept my two arrays as the only arguments, and return an array like this:

[
    [1,5],
    [3,0],
    [7,2]
]

The above array would be interpreted as "Move item at index 1 to index 5, then move item at index 3 to index 0, and finally move item at index 7 to index 2."

By an item-move operation I mean the following:

function arrayMove(array, from, to) {
    return array.splice(to, 0, array.splice(from, 1)[0]);
}

When an item is moved from index a to index b, items after index a "slide down" so the item that had index a + 1 now has index a, and when the item is added back at index b, the items that had an index >= b will slide up, so that the item that had index b would now have index b + 1.

Feel free to provide your algorithm in JS or pseudocode, any help appreciated.

Answer 1

Something like this perhaps?

Javascript

// swap two elements in an array by their indexes a and b and
// return an array of the swapped coordinates.
function swap(arr, a, b) {
    // assign the value at index a to temp
    var temp = arr[a];

    // assign the value at index b to index a
    arr[a] = arr[b];
    // assign the value of temp to the value at index b
    arr[b] = temp;

    // coordinates of move
    return [a, b];
}

// return an array of moved coordinates
function minMoves(arr1, arr2) {
    // take a shallow copy of arr2 so that the original is not modified
    arr2 = arr2.slice();

    // apply a function against an accumulator (moves) for each value of
    // the array (arr1) (from left-to-right)
    return arr1.reduce(function (moves, item, index) {
        // if the values of each array at the index are not the same
        if (item !== arr2[index]) {
            // swap the current indexed element of arr2 with the value of
            // the correct element as indexed in arr1. Add the moved
            // coordinates to the beginning of the accumulator
            moves.unshift(swap(arr2, index, arr2.lastIndexOf(item)));
        }

        // return the accumulater for the next iteration
        return moves;
    }, []);
}

var before = [1, 5, 6, 3, 2, 4, 7, 8, 9, 0],
    test = before.slice(),
    after  = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
    moves = minMoves(before, after);

console.log('moves: ' + JSON.stringify(moves));
moves.forEach(function(move) {
    swap(test, move[0], move[1]);
});

console.log('Should be ordered nicely: ' + JSON.stringify(test));

Output

moves: [[3,5],[2,5],[1,4]]
Should be ordered nicely: [1,2,3,4,5,6,7,8,9,0] 

On jsFiddle

This is what I would do, it is not based on any research of algorithms that have been proven optimal.

And here is the code using your arrayMove method instead of swap

Javascript

function arrayMove(array, from, to) {
    return array.splice(to, 0, array.splice(from, 1)[0]);
}

// return an array of moved coordinates
function minMoves(arr1, arr2) {
    // take a shallow copy of arr2 so that the original is not modified
    arr2 = arr2.slice();

    // apply a function against an accumulator (moves) for each value of
    // the array (arr1) (from left-to-right)
    return arr1.reduce(function (moves, item, index) {
        var last;

        // if the values of each array at the index are not the same
        if (item !== arr2[index]) {
            // swap the current indexed element of arr2 with the value of
            // the correct element as indexed in arr1. Add the moved
            // coordinates to the beginning of the accumulator
            last = arr2.lastIndexOf(item);
            arrayMove(arr2, last, index);
            moves.unshift([index, last]);
        }

        // return the accumulater for the next iteration
        return moves;
    }, []);
}

var before = [1, 5, 6, 3, 2, 4, 7, 8, 9, 0],
    test = before.slice(),
    after  = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
    moves = minMoves(before, after);

console.log('moves: ' + JSON.stringify(moves));
moves.forEach(function(move) {
    arrayMove(test, move[0], move[1]);
});

console.log('Should be ordered nicely: ' + JSON.stringify(test));

Output

moves: [[3,4],[2,5],[1,4]]
Should be ordered nicely: [1,2,3,4,5,6,7,8,9,0] 

On jsFiddle

Finally a jsPerf to compare the two methods.

Answer 2

This strikes me as related to the edit distance problem. Perhaps you could exploit the Wagner-Fischer algorithm.