4

ソース リストと宛先リストの 2 つのリストがあります。両方のリストはすべて同じ項目で構成されていますが、リストの順序が異なります。2 つのリストがある場合、リスト内の 1 つの項目を別の項目と交換し、最終的にソース リストを宛先リストと同じ順序にする一連のスワップ操作をソース リストで見つける必要があります。

この機能はデフォルトでは MPD にないため、MPD プレイリストをアルバムごとにシャッフルするスクリプトを作成しています。スクリプトは現在、現在のプレイリスト (ソース リスト) を取得し、リストのカスタム シャッフルを実行して、最終的に曲の新しい順序 (宛先リスト) を作成します。次に、スクリプトはプレイリストからすべてのアイテムを削除し、シャッフルされた新しいプレイリストの順序でそれらをプレイリストに挿入します。すべての曲を削除および追加する操作は時間がかかります。MPD ライブラリは、プレイリスト内の 2 つの曲の代わりのスワップをはるかに迅速に提供しますが、ソース リストを新しいシャッフル リストに変換する正しい一連のスワップ操作を見つける方法がわかりません。

これは Haskell で書かれていますが、どの言語/疑似コードでも問題ありません。

4

3 に答える 3

2 
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 から数え始めるという事実にあることに注意してください。

この実装では、2 番目のリスト内の位置に従って、最初のリスト内の要素に完全な順序付けを課すという考えを使用しています。次に、選択ソートを使用してスワップを取得します。これはおそらく最も効率的なソリューションではありませんが、有利なスタートを切るには良い方法です。

于 2012-12-31T11:44:41.433 に答える
1

簡単な方法は、宛先リストの順序を並べ替えの全順序として使用することです。たとえば、インデックスの順序を使用します。その場合、全順序関係はちょうど<インデックス上にあります。

次に、お気に入りの最も効率的なスワップベースの並べ替えアルゴリズムを実行して、最初のリストの全順序に一致するように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 %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になります。

QuickSortは、比較を最小限に抑えるのに最適であることに注意してください。 このページでは、選択ソート（最大O（n ^ 2）の比較が必要）は、少なくとも漸近的な最悪の場合の意味で、スワップの数を最小限に抑えると述べています。最大でn-1のスワップが必要です。実際、100個のアイテムでQuickSortを試したところ、156回のスワップが必要だったので、選択ソートの方が良かったでしょう。

于 2012-12-31T04:41:54.087 に答える
1

次の醜いコードを思いつきました。この考え方は、スワップベースのソート手法に似ています。2 つのリストがあるとします。

[7,1,2,4,3] および [2,3,4,1,7]

一度に 1 つのアイテムを交換できるようになりました。最初に最初の要素を正しく取得します。スワップをリストでスワップするインデックスのペアとして言及し、その後にスワップを適用した後に取得したリストが続きます

(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)]
于 2012-12-31T10:19:56.040 に答える