≡ Menu

Pancake sorting…

Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes.

Unlike traditional sorting algorithms, which attempt to sort with the fewest comparisons, pancake sort tries to sort the sequence in as few reversals as possible.

The idea behind pancake sort is similar to Selection Sort. In every iteration, we find the maximum element in the sequence and place it at the end, and reduce the size of the sequence by one.

Given an array of integers Arr:

  • Write a function flip(Arr, i) that reverses the order of the first i elements in the array arr.
  • Write a function pancakeSort(Arr) that sorts and returns the input array. You are allowed to use only the function flip in order to make changes in the array.

Algorithm :

Let the given array be Arr[] and size of the array be n

  • Start from the current size n and reduce the current size by one while it is greater than one. Let the current size be c. Do the following for every c.
    1. Find the index i of the maximum element in Arr[0....c-1].
    2. Call flip(Arr,i)
    3. Call flip(Arr,c-1)

Array representation of the above diagram :

initial pancake order : [3, 5, 2, 1, 7, 6, 4]

First flip : [3, 5, 2, 1, 7, 6, 4]
after first flip : [7, 1, 2, 5, 3, 6, 4]

Second flip : [7, 1, 2, 5, 3, 6, 4]
after second flip : [4, 6, 3, 5, 2, 1, 7]

Third flip : [4, 6, 3, 5, 2, 1, 7]
after third flip : [6, 4, 3, 5, 2, 1, 7]

Fourth flip : [6, 4, 3, 5, 2, 1, 7]
after fourth flip : [1, 2, 5, 3, 4, 6, 7]

Fifth flip : [1, 2, 5, 3, 4, 6, 7]
after fifth flip : [5, 2, 1, 3, 4, 6, 7]

Sixth flip : [5, 2, 1, 3, 4, 6, 7]
after sixth flip : [4, 3, 1, 2, 5, 6, 7]

Seventh flip : [4, 3, 1, 2, 5, 6, 7]
after seventh flip : [2, 1, 3, 4, 5, 6, 7]

Eight flip : [2, 1, 3, 4, 5, 6, 7]
after eighth flip : [1, 2, 3, 4, 5, 6, 7]

Below, the Python code that implements the algorithm explained:

…and the output:

Each pancake therefore requires two flips, which would give a total of \(2n\) flips required. But the last two pancakes require at most one flip; if they are already in order, no flips are needed, and if they are out of order, only one flip is needed. So this algorithm requires at most \(2(n – 2) + 1 = 2n – 3\) flips in the worst case, which means that \(P_n \leq 2n – 3\).

{ 0 comments }

…un po’ masochista.

Mi sono chiesto come mai mi piacciano i libri che mi fanno star male, “Non sarò un po’ masochista?”, mi son chiesto, e mi sono risposto con una cosa che mi è successa mentre scrivevo questo romanzo, nel gennaio del 2020. Ho partecipato alla riunione di una rivista che si chiama “Qualcosa”. L’argomento del numero di “Qualcosa” che stavamo preparando era: le storie sentimentali finite male; i disastri sentimentali, praticamente. Noi, quella sera lì, le venti persone che erano lì, di quei momenti che abbiamo passato tutti, che siam stati male per amore, se così si può dire, di quei giorni così dolorosi che eravamo messi così male che ci sembrava di non esser mai stati tanto male nella nostra vita, e non ci sembrava possibile stare peggio, a ripensarci dopo degli anni, ci veniva da pensare “Ma come son stato male bene, quel giorno lì. Ma che bello, essere così vivi”. Ecco. L’effetto che mi fa leggere (e rileggere) Delitto e castigo, Memorie del sottosuolo, L’idiota, I demoni, Il giocatore, I fratelli Karamazov è quello: mi accorgo di essere vivo, di avere un corpo, di avere il sangue che mi scorre nelle vene. Questo.

— Paolo Nori, Come mai mi piacciono. Novembre 2021

{ 0 comments }

Visualization with Matplotlib

Histogram

Histograms are one of the heavily used plots across functions as it gives a very good view of the distribution of data.

Line

Single line:

Several Lines

How do we add multiple lines in the same chart? Let us take it a bit further to plot multiple lines in the same chart.

Bar Plot

Bar plots are one of the most popular charts used in any type of visualization as it shows the relative data points in an emphasized manner like a line chart.

Scatter Plot

{ 0 comments }

The Julia Set

Fractals – a subset of Euclidean space with a fractal dimension that strictly exceeds its topological dimension – are one of my fondest topics in mathematics. I have always been fascinated by fractals, and the first piece of code I ever wrote was to create fractals.

The Julia set.

The Julia set is one of the most beautiful fractals to have been discovered. Named after the esteemed French mathematician Gaston Julia, the Julia set expresses a complex and rich set of dynamics, giving rise to a wide range of breathtaking visuals.

In this article, we will explore how to use Python to create the Julia set.

Complex Numbers

The Julia set lies on the complex plane, which is a space populated by complex numbers. Each point you see in the image above corresponds to a specific complex number on the complex plane with value: z = x + yi,
where i = √-1 is the imaginary unit.

Complex numbers have very interesting dynamics which is what gives the Julia set its complex dynamics, but for now let us take a look at real numbers, the numbers that we encounter in everyday life.

If you take the square of the real number 10, you get 100. Taking the square of 100 leads to 10,000. If we keep taking the square of the result, we get 100,000,000 in the next iteration, an astronomically large number in the next, and an even larger number in the next. Doing this enough times, we eventually tend to infinity, and we can say that the operation described is not bounded.

On the other hand, if you take the square of the real number 0.1, you get 0.01. Taking the square of 0.01 leads to 0.0001, and as with above if we keep taking the square of the result, we get 0.00000001 in the next number, a microscopically small number in the next and an even smaller number in the next. Doing this enough times we eventually tend to zero, and we can say that the operation described is bounded.

It turns out that complex numbers also behave similarly. If we take the square of the complex number 1 + i, we get 2i. If we square that we get -4. Repeating this we end up with 16, 256, 65536, 4294967296 and so on until we tend to infinity. This is similar to what happens if we iteratively square the result of the square of 10.

Likewise, if we take the square of 0.5 + 0.5i, we get 0.5i, -0.25, 0.0625, 0.00390625 and so on until we tend to 0. This is similar to what happens if we iteratively square the result of the square of 0.1.

Iterative Operations on the Complex Plane

Now instead of doing this iterative squaring operation on a single complex number, we can do this for an grid of complex numbers z lying on the complex plane. In addition to the squaring operation, we also add an arbitrary complex number c after the squaring operation to get the operation z := z + c.

After multiple iterations of z := z + c, most complex numbers in z will blow up to infinity, while some will remain bounded. During the iterative process we track how many iterations it takes for a complex number in z to blow up to infinity. It is this number of iterations measurement for each complex number in the grid that contains the image of the fractal in the image above.

Creating the Julia Set with Python

The Python code to create the Julia set is given below. The function julia_set takes the arguments c an arbitrary complex number, num_iter the number of iterations to perform, N the number of grid points on each axis in the grid, and X0 the limits of the grid.

import numpy as np
import matplotlib.pyplot as plt

def julia_set(c = -0.835 - 0.2321 * 1j, num_iter = 50, 
              N = 1000, X0 = np.array([-2, 2, -2, 2])):
    # Limits of the complex grid.
    x0 = X0[0] 
    x1 = X0[1]
    y0 = X0[2]
    y1 = X0[3]
    # Set up the complex grid. Each element in the grid
    # is a complex number x + yi.
    x, y = np.meshgrid(np.linspace(x0, x1, N), 
                       np.linspace(y0, y1, N) * 1j)
    z = x + y    
    # F keeps track of which grid points are bounded
    # even after many iterations of z := z**2 + c.
    
    F = np.zeros([N, N])    
    # Iterate through the operation z := z**2 + c.
    for j in range(num_iter):
        z = z ** 2 + c
        index = np.abs(z) < np.inf
        F[index] = F[index] + 1    
    
    return np.linspace(x0, x1, N), np.linspace(y0, y1, N), F

During each step in the for loop, after z = z ** 2 + c we check which points in z are still smaller than np.inf. The number of iterations taken by each point to blow up to infinity is recorded in F. By plotting F as a 2 dimensional image, the Julia set finally reveals itself. For example, the code below results in the image shown at the top of this post!

The light areas in the image correspond to points in the complex plane z that blow up to infinity very quickly after only several iterations, while the dark areas correspond to points that are bounded even after many iterations!

x, y, F = julia_set(c = 0.285 + 0.01 * 1j, num_iter = 200, 
                    N = 1000, X0 = np.array([-1.5, 1.5, -1.5, 1.5]))
plt.figure(figsize = (10, 10))
plt.pcolormesh(x, y, F, cmap = "gist_heat")
plt.axis('equal')
plt.axis('off')
plt.show()

As mentioned earlier, the Julia set has a rich and complex set of dynamics. This can be explored by changing the value of c! For example if we use the value c = -0.835–0.2321i, we get the visualization below, which is completely different from the previous one.

x, y, F = julia_set(c = -0.835 - 0.231 * 1j, num_iter = 200, 
                    N = 1000, X0 = np.array([-1.5, 1.5, -1.5, 1.5]))
plt.figure(figsize = (10, 10))
plt.pcolormesh(x, y, F, cmap = "gist_heat")
plt.axis('equal')
plt.axis('off')
plt.show()
Also the Julia set.

In fact, we can take things one step further, and define c to be the entire complex grid, by using c = x + y instead using the value of the input argument in the code above. In this case, the resulting fractal is so famous that it has its own name — the Mandelbrot set.

{ 0 comments }