Perfect shuffle

I have always been attracted to elementary algorithms with which you can create complex patterns. There is something fundamental in such algorithms. One of these algorithms is Perfect Shuffle. Let's look at its unusual properties, and also try to draw some impressive fractals using this algorithm.

Further there are a lot of pictures, gif-animations and some music.

Perfect Shuffle is known among gamblers-magicians. They call it Faro Shuffle. Recently, I also wanted to learn how to show card tricks. How do tricks begin? With the development of manual dexterity. After turning the pack of cards for a week, I mastered the basic ways of shuffling - “Riffle Shuffle”, “Faro Shuffle”, “Charlier Pass”. While practicing Faro Shuffle, I once arranged the deck so that all black suits are at the beginning of the deck, and the red suits are at the end. Having made Faro Shuffle several times, he paid attention to the unusual order of cards in the deck. Card postponed and sat down to program.

This algorithm changes the order of the elements in the array (shuffles the array). This algorithm is elementary:
')
1. We divide the array into two equal parts.
2. Elements from the first half of the array are placed in even positions. From the second - on the odd.

Clearly:



Even clearer:



The algorithm has several noteworthy properties. If you mix the array several times - after n iterations, all elements will return to their original position! It is obvious. The algorithm is deterministic. For each next state of the array, there is only one unique previous state. The number of all possible states is limited by the length of the array. If we mix the array iteratively, sooner or later we will exhaust the possible states and go through the second circle. In fact, it will happen much earlier. The number of iterations required to return the array to its initial state is less (or equal) to the number of elements in the array. “Less or equal” - all that can be said about the number of iterations.

For an array of 12 elements, 12 iterations will suffice:



For an array of 14 elements, only 4 iterations will suffice:



In the picture below (clickable) we mix arrays with lengths from 2 elements to 20:


(unshuffle)

The listed arrays are returned to their original state on
2, 4, 3, 6, 10, 12, 4, 8, 18, 6
iterations. Sequence A002326


Build a graph! On the graph on the X axis, we note the number of elements in the array (divided by 2). Y axis - the number of iterations. White dots denote the initial states of the arrays (the origin is the upper left corner):



Agree, the points on the chart are placed chaotically.

Another unusual property of Perfect Shuffle is that after a certain number of iterations, the order of the elements in the array may be reversed. Above in the picture we mixed an array of 12 elements. The order of the elements is reversed at the 6th iteration. Let's draw one more graph on which we will mark arrays with the reverse order of elements:



Again, the placement of points is no less chaotic.

It is very interesting to watch the movement of elements in the array! As elements from the first half of the array in the aggregate, and a specific (first) element in particular.

Fill the first half of the array with zeros, the second with units (hereafter, zeroes in the pictures are black pixels, ones are white). In the pictures below, each line ( X ) is an array state. Y - iteration.

Several arrays (142-150 elements):


Pictures are clickable

288 elements (144 * 2):



610 items:





As you can see, here too we have total chaos. Let's observe a separate element and its trajectory in the array.

An array of 610 elements. Only the first item is filled:



In general, for a single element, it is not necessary to mix the entire array. The position of a specific element at the next iteration can be calculated by the formula:


( Y is the length of the array)

The first arrays (with lengths from 2 to 22):



In the picture above: in the upper part of the picture is the array and the position of the element at each iteration, in the lower part of the line - all possible positions of the element. As you can see, the trajectory of the element inside the array is also not obvious. To finally verify this - from these lines we will make one more graph, adding them up as follows:


Clickable

Black pixels are those positions in the array that the first element does not fall into when mixed.

We could stop at this, but we will go even further! Observe the movement of all elements in the array. For this we go to the matrices.

But before moving on to the mixing of matrices, I will show two more foci with arrays.

In the second half of the array, we reverse the order of the elements (at each iteration):



In the second half we invert the elements:



These two operations will still be useful to us.

Let's go to the matrices!

Fill in the matrix, in the first row - the first element, in the second - the second, etc. In other words, draw a diagonal:



Shuffle the columns in the matrix using Perfect Shuffle. So we can see where all the elements fall after mixing. Matrix 80x80:



There is clearly lacking another diagonal:



A very curious moire is obtained. Matrix 242x242 from 27 to 35 iteration:



Well, if you have already started to mix columns in the matrix using Perfect Shuffle - why not mix the lines?

We modify our function a bit:


We divide the matrix into 4 parts. Mix the columns. Mix the strings. We get a new matrix. Clearly:



The diagonals shuffle are pretty boring:



It may even seem that in the function somewhere an error and the matrix is ​​not mixed. Shift the diagonals one pixel to the right:



Wonderful. The function works, the matrix is ​​mixed. True, again quite boring. Let's try to fill the matrix with some kind of pattern. In a random place draw a square:


The size of the matrix 80x80 was not chosen by chance. When mixing an array of 80 elements in length, at the 27th iteration, the order of the elements is reversed.

Let's move this square!



Here you can see one very interesting property, but even better this property is visible if you draw a circle:



Pay attention to edge effects. Our matrix collapses into a torus! This is clearly seen in the second iteration.

Move:




One of the interesting patterns:



We can make a fill to highlight closed areas:





Recall the tricks (reversing the order of elements and invert).

Changing the order of the elements gives very interesting patterns! One of them:



With fill:



Other patterns are no less interesting, but we will not dwell on them. It is much more interesting to watch the inversion.

For this experiment, we have enough of an empty matrix. Divide it into 4 parts. Two of them are inverted. Stir. At the first iteration, nothing unusual:



But further curious patterns appear:



To figure out where these patterns come from, let us go back to the arrays again. Before that, we used matrices and arrays of fixed length. Let's try to change the approach a little - we will gradually increase the length:

1. Create an array of n elements.
2. Make a copy of it.
3. Shuffle the copy with the original using Perfect Shuffle. Got an array of n * 2 elements.
4. Return to step 2.
We will invert the copy each time.

Let's start with an array of two elements - 1 and 0
10 - source array
10, 01 - array and inverted copy
0110 - mixed
0110, 1001 - array and inverted copy
10010110
10010110, 01101001
0110100110010110
… etc.

Received Morse-Thue sequence ( A010060 ) - the simplest fractal!

And back to the matrices. This is where pure art begins. Before that, we divided the matrix into 4 parts and mixed these parts. Let's try to copy the matrix, perform some elementary actions on copies and mix the original with copies.

With matrices we can produce 15 elementary actions. Action 0 - no change matrix. Steps 1-7 are different ways to rotate the matrix. Steps 8-15 are invert. Clearly:



As an example, we perform 0, 0, 7, 7 actions on copies. Step 7 - rotate the matrix by 90 °.



Next iteration:



... the eighth iteration:



A very unusual fractal turned out.



By combining the listed actions, you can draw 16 ^ 4 = 65536 fractals. Some of them:

Drawn in 6 iterations. Pictures are clickable (8 iterations).








But these pull on the masterpiece:

15, 5, 9, 5:


3, 5, 9, 5:


13, 7, 11, 11:


0, 0, 7, 13:


1, 1, 4, 14:


Other fractals can be drawn here.

These are the "card tricks" turned out. I think this can be temporarily stopped (you can mix three-dimensional matrix, but more on that another time).