How to swap items in place to transform one list in to another

Question

I have two lists: a source list and a destination list. Both lists consist of all the same items, but the lists are in a different order. Given the two lists, I need to find a series of swap operations on the source list that will swap one item in the list with another, eventually ending up with the source list in the same order as the destination list.

I am writing a script that shuffles an MPD playlist by albums, as this functionality is not in MPD by default. The script currently obtains the current playlist (the source list), performs a custom shuffle of the list, and end up with a new ordering of songs (the destination list). The script then removes all items from the playlist and inserts them back in to the playlist in the order of the new, shuffled playlist. Removing and adding all of the songs is a slow operation. The MPD library provides a much quicker in place swap of two songs in the playlist, but I do not know how to find the correct series of swap operations to transform the source list to the new shuffled list.

This is written in Haskell, but an 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 example above:

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

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

Note that the only difference in the results is in the order of the indices in swaps (which is a matter of convention) and the fact that I start counting elements from 0.

This implementation uses the idea of imposing a total ordering on the elements in the first list, according to where they are situated in the second list. It then uses Selection sort to get the swaps. It is probably not the most efficient solution, but good to give you a head start.

Answer 2

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

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

Now you can obtain swaps one item at a time. First get the first element correct, I have mentioned the swaps as pair of indexes to swap in the list followed by the list obtained after applying the 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 the swaps are

[(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 b a $ M.insert y i xm
            newmx = M.insert a b $ M.insert i y mx

In ghci

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

Answer 3

A simple way is to just use the destination list order as a total order for sorting. For example, use the index order. Then the total order relation is just < on the indices.

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

Here is a little throw-away 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's 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 a 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 do these swaps, the result is a to g in order, as you'd expect.

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 sense. It needs at most n-1 swaps. Indeed when I tried QuickSort on 100 items, it took 156 swaps, so selection sort would have been better.