How to swap in place to convert one list to another

Question

I have two lists: a source list and a mailing list. Both lists are made up of all the same elements, but the lists are in a different order. Given the two lists, I need to find a series of swap operations in the source list that will replace one element in the list with another, ending up with the source list in the same order as the mailing list.

I am writing a script that shuffles an MPD playlist by album, since by default this feature is not included in MPD. The script currently receives the current playlist (source list), performs a custom shuffle of the list, and ends with a new song order (destination list). Then the script removes all the elements from the playlist and inserts them back into the playlist in the order of the next shuffled playlist. Removing and adding all songs is slow. The MPD library provides a much faster replacement for two songs in a playlist, but I don’t know how to find the right series of swap operations to convert the original list to a new shuffled list.

This is written in Haskell, but the answer in any language / pseudo-code is fine.

Answer 1

import Data.List import Data.Maybe orderBySecond :: Ord a => (a, a) -> (a, a) -> Ordering orderBySecond (_, x1) (_, x2) = compare x1 x2 -- Gets the position in xs of elements in the second list (ys) indices :: Eq a => [a] -> [a] -> [(Int, Int)] indices xs ys = zip (map (\x -> fromJust $ x `elemIndex` xs) ys) [0 ..] getSwapsfromIndices :: [(Int, Int)] -> [(Int, Int)] getSwapsfromIndices xs = getSwapsfromIndices' xs [] -- The second argument for this is an accumulator used for tail recursion getSwapsfromIndices' :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)] getSwapsfromIndices' [] ys = ys getSwapsfromIndices' xs ys = getSwapsfromIndices' xs' (ys ++ new_swap) where (l1, l2) = minimumBy orderBySecond xs -- remove minimum from the list unordered = [ (x, y) | (x, y) <- xs, y /= l2] -- swap xs' = [ (if x == l2 then l1 else x, y) | (x, y) <- unordered] -- if no swap is needed, do not append anything new_swap = if l1 == l2 then [] else [(l1, l2)] swaps :: Eq a => [a] -> [a] -> [(Int, Int)] swaps xs ys = getSwapsfromIndices $ indices xs ys 

By running the code with the above example:

 *Main> swap [2,3,4,1,7] [7,1,2,4,3] [(4,0),(3,1),(4,2),(4,3)] 

Please note that the only difference in the results is in the order of the indices in the swaps (which is conditional) and in the fact that I start to count elements from 0.

This implementation uses the idea of ​​superimposing full order on elements in the first list, depending on where they are in the second list. Then it uses selection sorting to get swaps. This is probably not the most effective solution, but it is helpful to give you a start.

Answer 2

A simple way is to simply use the mailing list order as a general sort order. For example, use index order. Then the total order relation is simply < in the indices.

Now run your favorite, most efficient swap-based sorting algorithm to sort the second list so that it matches the full order of the first. (Quicksort comes to mind.) Each time a sort makes a swap, record the pair in sequence. This sequence is your answer.

Here is a little C code to show you what I'm talking about:

 #include <stdio.h> #include <stdlib.h> #include <string.h> // A faux play list item. struct list_item { char name[9]; int index; }; // Randomized quicksort that prints its swaps. // Note this sorts on the 'index' field, which defines the total order. void sort(struct list_item **a, int n) { if (n <= 1) return; struct list_item *p = a[rand() % n]; int lo = 0; int hi = n - 1; while (lo <= hi) { while (a[lo]->index < p->index) ++lo; while (a[hi]->index > p->index) --hi; if (lo < hi) { // We need a swap! Print it! printf("swap %s and %s\n", a[hi]->name, a[lo]->name); struct list_item *t = a[lo]; a[lo] = a[hi]; a[hi] = t; ++lo; --hi; } else if (lo == hi) { ++lo; --hi; } } sort(a, hi + 1); sort(a + lo, n - lo); } // Make an array of pointers to simulated play list items. struct list_item **make_list(int n) { int j; struct list_item **a = malloc(n * sizeof(struct list_item *)); char x[9] = "a"; for (int i = 0; i < n; i++) { a[i] = malloc(sizeof(struct list_item)); strcpy(a[i]->name, x); for (j = 0; x[j] == 'z'; j++) x[j] = 'a'; x[j] = x[j] ? x[j] + 1 : 'a'; } return a; } // Randomize a list of pointers. void randomize_list(struct list_item **a, int n) { for (int i = 0; i < n - 1; i++) { int r = i + rand() % (n - i); struct list_item *t = a[r]; a[r] = a[i]; a[i] = t; } } // Test case size. #define N 7 int main(void) { // Make a nice test destination list.. struct list_item **dst = make_list(N); // Make a copy of the pointers and shuffle them to make the source list. struct list_item **src = malloc(N * sizeof(struct list_item *)); memcpy(src, dst, N * sizeof(struct list_item *)); randomize_list(src, N); // Print the source to see where we're starting. for (int i = 0; i < N; i++) printf("%d: %s\n", i + 1, src[i]->name); // Define the total order to be the destination index order. for (int i = 0; i < N; i++) dst[i]->index = i; // Sort the source to duplicate the destination. // Swaps printed above will get the job done. sort(src, N); return 0; } 

And the result for a list of length 7:

 1: g 2: a 3: b 4: d 5: c 6: f 7: e swap e and g swap c and e swap a and c swap b and c 

If you perform these swaps, the result will be g, as you would expect.

Please note that QuickSort is great for minimizing comparisons. This page says that Selection Sort (which requires up to O (n ^ 2) comparisons) minimizes the number of swaps, at least in the asymptotic worst case feeling. It requires no more than n-1 swaps. Indeed, when I tried QuickSort on 100 elements, it took 156 swaps, so sorting would be better.

Answer 3

I came up with the following ugly code. The idea is similar to a swap-based sorting method. Suppose you have two lists

[7,1,2,4,3] and [2,3,4,1,7]

Now you can receive swaps one item at a time. First, return the first element, I mentioned swaps as a pair of indexes to replace in the list, followed by the list obtained after applying swap

(1,5) => [7,3,4,1,2]

(2,4) => [7,1,4,3,2]

(3,5) => [7,1,2,3,4]

(4,5) => [7,1,2,4,3]

So swaps

[(1,5), (2,4), (3,5), (4,5)]

 import qualified Data.Map as M import Data.Maybe -- It will totally break if lists don't contain same items. swaps :: Ord a => [a] -> [a] -> [(Int,Int)] swaps xs ys = reverse . getFirst $ foldl f ([],xsm,mxs,1) ys where getFirst (a,_,_,_) = a xsm = M.fromList $ zip xs ([1..]) -- Construct map for O(logn) lookups mxs = M.fromList $ zip ([1..]) xs -- Map for Reverse lookup f (swps,xm,mx,i) y = if i==a then (swps,newxm,newmx,i+1) else ((i,a):swps,newxm,newmx,i+1) where a = fromJust $ M.lookup y xm -- Not very safe to use fromJust b = fromJust $ M.lookup i mx newxm = M.insert ba $ M.insert yi xm newmx = M.insert ab $ M.insert iy mx 

In ghci

 *Main> swaps [2,3,4,1,7] [7,1,2,4,3] [(1,5),(2,4),(3,5),(4,5)]