如何在适当位置交换项以将一个列表转换为另一个列表

Question

我有两个列表:源列表和目标列表。两个列表都包含相同的项目，但列表的顺序不同。给定这两个列表，我需要在源列表上找到一系列交换操作，将列表中的一个项与另一个项交换，最终得到与目标列表顺序相同的源列表。

我正在编写一个脚本，按专辑打乱MPD播放列表，因为默认情况下此功能不在MPD中。脚本当前获取当前播放列表(源列表)，执行列表的自定义洗牌，并以新的歌曲排序(目标列表)结束。然后，脚本从播放列表中删除所有项目，并按照新的、洗牌的播放列表的顺序将它们插入到播放列表中。删除和添加所有的歌曲是一个缓慢的操作。MPD库在播放列表中提供了更快的两首歌曲的就地交换，但我不知道如何找到正确的交换操作系列来将源列表转换为新的洗牌列表。

这是用Haskell写的，但任何语言/伪代码的答案都可以。

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

通过运行上面的示例代码:

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

请注意，结果的唯一区别在于交换中索引的顺序(这是惯例问题)以及我从0开始计数元素的事实。

这个实现使用了对第一个列表中的元素根据它们在第二个列表中的位置施加总排序的思想。然后它使用选择排序来获得交换。这可能不是最有效的解决方案，但可以为您提供良好的开端。

Answer 2

一种简单的方法是仅使用目标列表顺序作为排序的总顺序。例如，使用索引顺序。则总序关系仅为指标上的<。

现在运行您最喜欢的、最有效的基于交换的排序算法，对第二个列表进行排序，使其符合第一个列表的总顺序。(我想到了快速排序。)每次排序进行交换时，将对记录在一个序列中。这个序列就是你的答案。

这里有一个简单的C代码来告诉你我在说什么:

#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 %sn", 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: %sn", 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;
} 

和长度为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

如果你做这些交换，结果是a到g的顺序，正如你所期望的。

请注意，快速排序对于最小化比较非常有用。本页说，选择排序(需要多达O(n^2)次比较)最小化交换次数，至少在渐进的最坏情况下是这样。它最多需要n-1次交换。事实上，当我尝试对100个项目进行快速排序时，需要进行156次交换，所以选择排序可能会更好。

Answer 3

我编写了以下丑陋的代码。这个想法类似于基于交换的排序技术。假设您有两个列表

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

现在你可以一次换一个物品。首先使第一个元素正确，我已经提到了交换作为列表中要交换的索引对，然后是应用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)

所以互换是

[(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

在ghci

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