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

Question

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

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

这么说，我的意思是在执行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' 复制该元素留下一个空的 space，然后从左向右移动数组，以便将空的 space 精确地移动到位置 'p'，一旦完成，代码就移动到数据 [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 与左侧的元素块 [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

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

当您取消打乱时，您必须还原这些步骤：对于偶数大小的数组，在最后一个元素处开始 lo 和 hi，对于奇数大小的数组，在数组之外的一个元素处开始。然后以相反的顺序执行所有步骤：先减少 lo 和 hi，然后向左移动块并将旧的 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;
    }    
}

我删除了左右索引，这使得代码不太灵活，但希望更清晰易读。您可以将它们放回去，只需要它们来计算 lo 和 hi.

的初始值

Answer 2

您可以使用固定数量的交换执行这两个步骤，但代价是 non-linear 指数计算步骤。但对于实际应用，交换的时间成本通常驱动总时间，因此这些算法接近 O(N)。

对于完美的洗牌，请参阅 https://cs.stackexchange.com/a/105263/58310 (or https://cs.stackexchange.com/q/105604/58310 的替代解释）

对于unshuffling，这里描述了一个相关的算法：

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

Perfect shuffle and unshuffle, with no auxiliary array

c++

algorithm

shuffle