c++ - 完美的shuffle和unshuffle，没有辅助数组

Question

在任何具体问题之前，请注意我的目标不是随机洗牌，而是像理想的发牌者对一组牌那样进行完美洗牌，即将一副牌分成两半，执行一次洗牌(将半副牌中的一张牌与另一半副牌中的一张牌交错)。 (这实际上是 Sedgewick 的 Algorithms in C 第三版中的一项练习:nbr 11.3 第 445 页)

所以，我对 Fisher-Yates shuffle 等算法不感兴趣。

也就是说，我的观点是在执行洗牌时避免使用任何辅助数组，我能够提供的代码如下:

template<typename T>
void two_way_shuffle(vector<T>& data,int l,int r)
{
    int n=(r-l)+1;
    int m=(r+l)/2;
    if(n%2==0) ++m;
    int s,p{l+1};
    for(;p<=r;p+=2,m++)
    {
        s=data[m]; //Make space
        //Shift the elements
        for(int i{m};i>p;i--)
            data[i]=data[i-1];
        //Put the element in the final position
        data[p]=s;
    }
}


template<typename T>
void two_way_unshuffle(vector<T>& data,int l,int r)
{
    int n=(r-l)+1;
    if(n%2!=0){
        --r;
        --n;
    }
    int m=(r+l)/2;
    int s,p{l+1},w{r-1};
    for(;p<=w;p++,w--)
    {
        s=data[w];
        for(int i{w};i>p;i--)
            data[i]=data[i-1];
        data[p]=s;
    }
    //Complete the operation
    for(p=l+1,w=m;p<w;p++,w--)
        swap(data[p],data[w]);
}

洗牌操作的基本思想是跟踪数组“p”中应该插入下一个元素的位置，然后从数组数据中的位置“w”复制该元素，留下一个空白空间，然后将数组从左向右移动，以便将空白空间准确移动到位置“p”，一旦完成，代码只需移动到 data[p] 之前保存的值“s”。很简单..它看起来工作正常(一些洗牌的例子)

FROM: 12345678
TO:   15263748

FROM: IS THIS WORKING CORRECTLY OR NOT?
TO:   ICSO RTRHEICST LWYO ROKRI NNGO T?

FROM: SHUFFLING TEST
TO:   SNHGU FTFELSIT

我的问题是在 unshuffle 操作中，我相信可以避免最后一个 for 循环中的交换序列，但我无法找到切肉刀的方法来做到这一点。问题在于主循环 unshuffle 执行移位操作，最终以错误的顺序留下数组前半部分的元素(因此，需要在第二个 for 中进行交换)。

我几乎可以肯定必须有一种聪明的方法来完成这项工作而不会出现这样的代码复杂性..

对于 unshuffle 算法可以改进的地方，您有什么建议吗？或者对我所做的任何其他建议？

谢谢

Answer 1

我认为您的代码保留了太多变量。当你打乱数组时，你正在处理一个大小递减的范围 [lo, hi]，你将最右边的条目 hi 与左边的元素 block 交换 [lo, hi)。您可以仅根据这两个变量来表达算法:

0  1  2  3  4  5
   -------              swap [1, 3) and [3]
0  3  1  2  4  5
         ----           swap [3, 4) and [4]
0  3  1  4  2  5
               -        [5, 5) is empty: break

这对于奇数个元素是一样的，只是空范围超出了界限，这没关系，因为我们不访问它。这里的操作是:右移 block ，将旧的hi元素放在lo位置，增加lo和hi步幅 2 和 1。

当你取消洗牌时，你必须恢复这些步骤:在最后一个元素开始 lo 和 hi 对于偶数大小的数组和超出数组的一个元素对于奇数大小的数组.然后以相反的顺序执行所有步骤:首先减少 lo 和 hi，然后将 block 向左移动并将旧的 lo 放在 hi 位置。当 lo 达到 1 时停止。(它将达到 1，因为我们从一个奇数索引开始并且我们递减 2。)

您可以通过打印 lo 和 hi 来测试您的算法:它们对于洗牌和取消洗牌必须相同，只是顺序相反。

所以:

template<typename T>
void weave(std::vector<T>& data)
{
    size_t lo = 1;
    size_t hi = (data.size() + 1) / 2;

    while (lo < hi) {
        T m = data[hi];

        for (size_t i = hi; i-- > lo; ) data[i + 1] = data[i];

        data[lo] = m;
        lo += 2;
        hi++;
    }
}

template<typename T>
void unweave(std::vector<T>& data)
{
    size_t n = data.size();
    size_t lo = n + n % 2 - 1;
    size_t hi = lo;

    while (hi--, lo-- && lo--) {
        T m = data[lo];

        for (size_t i = lo; i < hi; i++) data[i] = data[i + 1];

        data[hi] = m;
    }    
}

我删除了左右索引，这降低了代码的灵 active ，但希望更清晰易读。您可以将它们放回去，只需要它们来计算 lo 和 hi 的初始值。