使用有限的操作对双端队列进行排序？

Question

您好，我在 Robert Sedgewick 的算法第 4 版中遇到了一个问题。

Dequeue sort. Explain how you would sort a deck of cards, with the restriction that the only allowed operations are to look at the values of the top two cards, to exchange the top two cards, and to move the top card to the bottom of the deck.

我希望有人能解释这是如何完成的，我真的迷路了。谢谢

Answer 1

与其想一副有顶有底的牌，不如想象一副纸牌排列成一个环。您可以想象在两张特定卡片之间放置一个标记，然后对应于牌组的顶部。你的"swap the top two cards"操作就是将两张牌交换到标记的左边，然后"move the top of the deck to the bottom"的操作对应于将标记向左移动一步。

鉴于此，您自然可以调整冒泡排序以在此设置中工作。将环中的一个位置永久标记为起点。然后，重复执行以下操作：如果标记左侧的两张牌顺序不对，则交换它们。然后，将标记向左移动一步。作为规则的例外，如果标记比标记的初始位置早一步，则不要进行比较。绕一圈不换东西就完了！

在伪代码中，这看起来如下：

repeat the following until no swaps are made:
    counting from i = 1 to n - 1, inclusive:
       if the top two cards are out of order, swap them.
       move the top card of the deck to the bottom.
    then, move the top card of the deck to the bottom.

希望对您有所帮助！

Answer 2

我有一个对我来说非常简单的策略：

认为这与冒泡排序相同：1）比较（可能交换）然后移动； 2）不要比较和移动（不要改变顺序）。并且两种动作在一轮内走52步（甲板的长度）。

条件一：

def exchange_move(cards): 
    if cards[0] > cards[1]:
        cards[0], cards[1] = cards[1], cards[0]
        cards.append(cards.popleftL())
    else:    
        cards.append(cards.popleft())

条件二：

def move(cards): 
    cards.append(cards.popleft())

并在每一轮中采取这两种行动：

for i in range(card_len-skip):
    exchange_move(cards)
for i in range(skip)
    move(cards)

这是 Python 中的完整代码：

from collections import deque
import random
from enum import Enum

class Suit(Enum):
    __order__ = "spade heart club diamond"
    spade = 1
    heart = 2
    club = 3
    diamond = 4


class Card(object):
    def __init__(self, suit, value):
        assert type(suit) == Suit
        assert value > 0 and value < 14
        self._suit = suit
        self._value = value
        self.value = self._get_value()

    def _get_value(self):
        return self._suit.value * 13 + self._value

    def __lt__(self, other):
        return self.value < other.value

    def __str__(self):
        return str((self._suit.name, self._value))

cards = deque(maxlen=52)

for s in Suit:
    for i in range(13):
        cards.append(Card(s, i+1))

random.shuffle(cards)

def is_sorted(cards):
    for i in range(len(cards)-2):
        if cards[i] > cards[i+1]:
            return False
    return True

def exchange_move(cards):
    if cards[0] > cards[1]:
        cards[0], cards[1] = cards[1], cards[0]
    cards.append(cards.popleft())

def move(cards):
    cards.append(cards.popleft())

skip = 0
while(not is_sorted(cards)):
    if skip == len(cards):
        print('something strange happened')
    for i in range(len(cards)-skip):
        exchange_move(cards)
    for i in range(skip):
        move(cards)
    skip += 1

for c in cards:
    print(c)

Answer 3

此处使用 java 是一个非常简单的解决方案。只需通过比较并跟踪已排序元素的数量来不断移动顶部元素。在每次迭代中，它都会根据位置给我们一个最小的元素。我们将根据 n 和 k 值执行此操作。对于 n 值，我们将继续基于更大的元素移动，对于 k 值，我们将继续基于更小的值移动，最终，解决方案将会出现。你可以试试这个。

private void sort(Integer[] a) {
        int n = a.length-1,k=1;
        while (n>0){
            for (int i = 0; i < n; i++) {
                if (a[1]>a[0]){
                    int temp = a[0];
                    a[0] = a[1];
                    a[1] = temp;
                }
                pushToBackAndShift(a);
            }
            for (int i = 0; i < k; i++) {
                if (a[1]<a[0]){
                    int temp = a[0];
                    a[0] = a[1];
                    a[1] = temp;
                }
                pushToBackAndShift(a);
            }
            n--;k++;
        }
        pushToBackAndShift(a);
    }

private void pushToBackAndShift(Integer[] a) {
        int temp = a[0];
        for (int i = 0; i < a.length-1; i++) {
            a[i] = a[i+1];
        }
        a[a.length-1] = temp;
    }

使用有限的操作对双端队列进行排序？

Sorting a deque using limited operations?

algorithm

sorting

deque