arrays - 如何交换项目以将一个列表转换为另一个列表

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 开始计算元素的事实。

此实现使用了根据第一个列表中的元素在第二个列表中的位置对第一个列表中的元素进行总排序的想法。然后它使用选择排序来获取交换。它可能不是最有效的解决方案，但很高兴为您提供一个良好的开端。