我有两个列表：源列表和目标列表。两个列表都包含所有相同的项目，但列表的顺序不同。给定这两个列表，我需要在源列表上找到一系列交换操作，将列表中的一个项目与另一个项目交换，最终以与目标列表相同的顺序结束源列表。
我正在编写一个按专辑随机播放 MPD 播放列表的脚本，因为默认情况下此功能不在 MPD 中。该脚本当前获取当前播放列表（源列表），执行列表的自定义随机播放，并以新的歌曲顺序（目标列表）结束。然后，该脚本会从播放列表中删除所有项目，并按照新的打乱播放列表的顺序将它们重新插入到播放列表中。删除和添加所有歌曲是一项缓慢的操作。MPD 库为播放列表中的两首歌曲提供了更快的就地交换，但我不知道如何找到正确的一系列交换操作来将源列表转换为新的随机列表。
这是用 Haskell 编写的，但任何语言/伪代码的答案都可以。
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.
一种简单的方法是仅使用目标列表顺序作为排序的总顺序。例如，使用索引顺序。那么总顺序关系就<在索引上。
现在运行您最喜欢的、最有效的基于交换的排序算法，对第二个列表进行排序以符合第一个列表的总顺序。（想到快速排序。）每次排序进行交换时，按顺序记录这对。这个序列就是你的答案。
下面是一些一次性的 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 %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;
}
长度为 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，正如您所期望的那样。
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.
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)]