Perfect shuffle and unshuffle, with no auxiliary array

Question

Before any concrete question, please note that my goal is not to shuffle randomly the array, but to perform a perfect shuffle as the one a ideal dealer may do with a set of cards, that is, splitting the deck in half and performing one shuffle passage (interleaving a card from one half deck with one card from the other half). (This is actually one exercise from Algorithms in C third edition by Sedgewick: nbr 11.3 page 445)

So, i'm not interested in algorithms like Fisher-Yates shuffle etc.

Said that, my point is to avoid using any auxiliary array when performing the shuffle, the code I was able to deliver is the following:

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]);
}

The basic idea beside the shuffling operation is to keep track of the position in the array 'p' where the next element should be inserted, then copying that element from the array data at position 'w' leaving one empty space, then shifting the array from left to right in order to move the empty space exactly to the position 'p', once that was done the code just move to data[p] the previously saved value 's'. Pretty simple.. And it looks to work properly (some shuffle examples)

FROM: 12345678
TO:   15263748

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

FROM: SHUFFLING TEST
TO:   SNHGU FTFELSIT

My very problem is in the unshuffle operation, I believe that the swap sequence in the last for loop can be avoided, but I'm not able to find a cleaver way to do that. The problem is that the main loop unshuffle performs a shift operation which eventually leave the elements of the first half of the array in the wrong order (thus, requiring the swap in the second for).

I'm almost sure there must be a clever way to do the job without such a code complication..

Do you have any suggestion on what may be improved in the unshuffle algorithm? Or any other suggestion on what I've done?

Thanks

Let's call it "Objectless c++". Seriously, shouldn't we create a tag named "Objectless C++"? — user3528438, May 22 '15 at 12:32
I think you did the natural thing. This one is more efficient but much more complicated http://stackoverflow.com/questions/12338654/move-all-odd-positioned-element-to-left-half-and-even-positioned-to-right-half-i — vib, May 22 '15 at 12:35
@user3528438 Why would you call it "Objectless C++"? Not only do you have an object `vector& data` but you are also using templates. — NathanOliver, May 22 '15 at 12:38
Idiomatic c++ doesn't need to involve classes or any kind of oop, calling it c just because there is no class hierarchy is misguided. — Cubic, May 22 '15 at 17:09

score 0 · Accepted Answer · answered May 22 '15 at 16:15

I think your code keeps too many variables. When you shuffle the array, you are treating a range [lo, hi] of decreasing size, where you swap the rightmost entry hi with the block of elements to te left [lo, hi). You can express the algorithm just in terms of these two variables:

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

This is the same for an odd number of elements, except that the empty range goes out of bound, which is okay, since we don't access it. The operations here are: shift block right, place old hi element at lo position, increase lo and hi with strides 2 and 1.

When you unshuffle, you must revert the steps: Start lo and hi at the last element for even-sized and one element beyond the array for odd-sized array. Then do all steps in reverse order: decrease lo and hi first, then shift the block left and place the old lo at hi position. Stop when lo reaches 1. (It will reach 1, because we've started at an odd index and we decrement by 2.)

You can test your algorithm by printing lo and hi as you go: They must be the same for shuffling and unshufling, only in reverse order.

So:

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;
    }    
}

I've removed the left and right indices, which makes the code less flexible, but hopefully clearer to read. You can put them back in and will only need them to calculate your initial values for lo and hi.

score 0 · Answer 2 · answered Apr 12 '22 at 04:38

You can perform both these steps with a fixed number of swaps, at the cost of a non-linear index calculation step. But for practical applications the time cost of the swap usually drives the total time, so these algorithms approach O(N).

For perfect shuffling, see https://cs.stackexchange.com/a/105263/58310 (or https://cs.stackexchange.com/q/105604/58310 for an alternate explanation)

For unshuffling, a related algorithm is described here: https://stackoverflow.com/a/55112294/10396

Perfect shuffle and unshuffle, with no auxiliary array

2 Answers2