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.

It's a good puzzle, but so far it shows no effort on your part. Can you show us what attempts you've got at an algorithm so far? — Jonathan M, May 15 '14 at 21:07
@JonathanM I've looked around, and found [this question](http://stackoverflow.com/questions/10630659/algorithm-for-expressing-reordering-as-minimum-number-of-object-moves), but no actual code was provided as an answer. — Web_Designer, May 15 '14 at 21:08
The question ... is not there. It reads like a problem description, where you've graciously given us permission to humbly present our ideas in JS or pseudocode. — Stefan Schmiedl, May 15 '14 at 21:09
When moving index 1 to index 5, what happens to indices 2, 3, 4 and 5? Do 2, 3 and 4 slide to a lower-number index and 5 slides up to 6? Or is moving 1 to 5 basically swapping the two? Define "move". — Jonathan M, May 15 '14 at 21:10
I think this is what you are looking for - http://stackoverflow.com/questions/6229197/how-to-know-if-two-arrays-have-the-same-values — Sid, May 15 '14 at 21:20
@Sid, no, he's wanting the moves necessary to make them identical. — Jonathan M, May 15 '14 at 21:22
@JonathanM Reordering elements in the DOM to match a sorted array using the least number of DOM mods possible. — Web_Designer, May 15 '14 at 21:28
Why not just create a custom sort function for the DOM elements themselves? — Jonathan M, May 15 '14 at 21:30
@Web_Designer: I wondered if that was the application. In that case, and if the DOM is large enough that it makes sense to care about optimising this at all, then beware that shunting all remaining elements forward or backward is a time-consuming O(n) operation, so the overall time complexity is O(n^2). You'll be much better off *swapping* elements, which is O(1) per operation, for O(n) overall. — j_random_hacker, May 16 '14 at 05:24

thus spake a.k. · Answer 1 · 2014-05-15T21:59:20.897

1

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

edited May 15 '14 at 21:59

answered May 15 '14 at 21:45

thus spake a.k.

1,607
12
12

Xotic750 · Answer 2 · 2014-05-16T03:02:39.570

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.

Doesn't seem to be working when I mutate the *before* array to look like the *after* array using the moves outputted: http://jsbin.com/dafewi/1/edit?javascript,console,output — Web_Designer, May 16 '14 at 01:14
`arrayMove` doesn't do the same thing as `swap`. `arrayMove` cuts a values from the array, puts it in place and moves the rest of the items to the right. `swap` exchanges the positions of two items and leaves the rest alone. — Xotic750, May 16 '14 at 02:13
Here it is using your `arrayMove` : http://jsfiddle.net/Xotic750/Czwnu/ but now it takes an extra move `[[4,1],[3,1],[2,5],[1,4]]`. "how to make a list of least number of item-move operations required to make arr1 match arr2?" — Xotic750, May 16 '14 at 02:18
Thanks! I'm curious, why do you use JSFiddle instead of JS Bin? — Web_Designer, May 16 '14 at 02:20
Suits my screen size and style of working better (I use the actual console) — Xotic750, May 16 '14 at 02:21
And I didn't get the code correct with using `arrayMove`. I will update the fiddle when I get time. — Xotic750, May 16 '14 at 02:26
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/52801/discussion-between-web-designer-and-xotic750) — Web_Designer, May 16 '14 at 02:34
Updated it, now `arrayMove` has the same number of moves as `swap` but the indexing is different because of the different methods `[[3,4],[2,5],[1,4]]` — Xotic750, May 16 '14 at 02:34

diff 2 arrays where items were simply reordered

2 Answers2