[FIXED] What mathematical or memory trick does numpy.flatten() use on numpy.transform?

Issue

I am trying to replicate transpose + flatten method of numpy. In order to take transpose, I only swap the last dimension with the dimension I want to transpose. Then I transform item positions to
linear index. However item ordering comes out different with numpy.flatten(). How can i achieve same behavior? Desired output is numpy flatten output. The question is how does numpy achieve this?

Here is the example:

Step 1:
Let's say I have an 1d array of K=16 sequential integers:

1d_Arr = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])`

Step 2:
I reshape it to (2,2,4) dimensions. (row, col, depth) == (2,2,4)

3d_Arr = 1d_Arr.reshape((2,2,4))

Step 3:
Take dimension-wise transpose.
Notice they all swapped with the last index of the 3d_Arr.shape.

row_transpose   = 3d_Arr.transpose((2,1,0)).flatten()
col_transpose   = 3d_Arr.transpose((0,2,1)).flatten()
depth_transpose = 3d_Arr.transpose((0,1,2)).flatten()

Step 4:
Print indices by using:

# returns where is the element in the array. Such as (2,0,1)
# i: is a value of an array item.
indices = np.where(anArray == i)
# returns the current (some?) linear index for the given indices
linear_idx = np.ravel_multi_index(indices, anArray.shape)

Results:

1d_Array (Linear) :

[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15] 

---

Desired output:

row-transpose-flatten   = [ 0  8  4 12  1  9  5 13  2 10  6 14  3 11  7 15]  
col-transpose-flatten   = [ 0  4  1  5  2  6  3  7  8 12  9 13 10 14 11 15]  
depth-transpose-flatten = [ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15]`  

---

My strategy

DEPTH-TRANSPOSE :

Element Value -> Element indices -> ravel_multi_index for Element indices

0 ->  (array([0]), array([0]), array([0])) ->  [0]
1 ->  (array([0]), array([0]), array([1])) ->  [1]
2 ->  (array([0]), array([0]), array([2])) ->  [2]
3 ->  (array([0]), array([0]), array([3])) ->  [3]
4 ->  (array([0]), array([1]), array([0])) ->  [4]
5 ->  (array([0]), array([1]), array([1])) ->  [5]
6 ->  (array([0]), array([1]), array([2])) ->  [6]
7 ->  (array([0]), array([1]), array([3])) ->  [7]
8 ->  (array([1]), array([0]), array([0])) ->  [8]
9 ->  (array([1]), array([0]), array([1])) ->  [9]
10 ->  (array([1]), array([0]), array([2])) ->  [10]
11 ->  (array([1]), array([0]), array([3])) ->  [11]
12 ->  (array([1]), array([1]), array([0])) ->  [12]
13 ->  (array([1]), array([1]), array([1])) ->  [13]
14 ->  (array([1]), array([1]), array([2])) ->  [14]
15 ->  (array([1]), array([1]), array([3])) ->  [15]

ROW-TRANSPOSE :

Element Value -> Element indices -> ravel_multi_index for Element indices

0 ->  (array([0]), array([0]), array([0])) ->  [0]
1 ->  (array([1]), array([0]), array([0])) ->  [4]
2 ->  (array([2]), array([0]), array([0])) ->  [8]
3 ->  (array([3]), array([0]), array([0])) ->  [12]
4 ->  (array([0]), array([1]), array([0])) ->  [2]
5 ->  (array([1]), array([1]), array([0])) ->  [6]
6 ->  (array([2]), array([1]), array([0])) ->  [10]
7 ->  (array([3]), array([1]), array([0])) ->  [14]
8 ->  (array([0]), array([0]), array([1])) ->  [1]
9 ->  (array([1]), array([0]), array([1])) ->  [5]
10 ->  (array([2]), array([0]), array([1])) ->  [9]
11 ->  (array([3]), array([0]), array([1])) ->  [13]
12 ->  (array([0]), array([1]), array([1])) ->  [3]
13 ->  (array([1]), array([1]), array([1])) ->  [7]
14 ->  (array([2]), array([1]), array([1])) ->  [11]
15 ->  (array([3]), array([1]), array([1])) ->  [15]`

As it can be seen above, The strategy for flatten() operation is different. Numpy flatten output pattern and my strategy gives different outputs. Desired output is numpy flatten output.
The question is how does numpy achieve this ?

Solution

Your base arrays, with proper names:

In [827]: Arr1 = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
     ...: Arr3 = Arr1.reshape((2,2,4))

The key multidimension information:

In [828]: Arr3.base, Arr3.shape, Arr3.strides, Arr1.strides
Out[828]: 
(array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15]),
 (2, 2, 4),
 (32, 16, 4),
 (4,))

Step one element is done with 4 bytes. That's true for Arr1 and the columns (last dim) of Arr3. Step rows of Arr3 by 4 elements. Step planes (1st dim) by 32, i.e. 2 rows.

One of the your transposes:

In [830]: x=Arr3.transpose((2,1,0)); x.base, x.shape, x.strides
Out[830]: 
(array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15]),
 (4, 2, 2),
 (4, 16, 32))

Same strides, but reversed order, as is the shape. It's a view, same Arr1 base.

In [831]: x.reshape(-1)
Out[831]: array([ 0,  8,  4, 12,  1,  9,  5, 13,  2, 10,  6, 14,  3, 11,  7, 15])

flatten/ravel is same as reshape to 1d. Display x to better visualize how it is flattened.

Making a (2,2,4) version:

In [834]: Arr3.transpose((1,0,2))
Out[834]: 
array([[[ 0,  1,  2,  3],
        [ 8,  9, 10, 11]],

       [[ 4,  5,  6,  7],
        [12, 13, 14, 15]]])

In [835]: Arr3.transpose((1,0,2)).flatten()
Out[835]: array([ 0,  1,  2,  3,  8,  9, 10, 11,  4,  5,  6,  7, 12, 13, 14, 15])

In [836]: Arr3.transpose((1,0,2)).strides
Out[836]: (16, 32, 4)

Still step 4 bytes, 1 element on the last dim, but 32 instead of 16 to step rows.

With the shape/strides formulation, you don't need a special formula for each transpose. The same stepping applies regardless of shape and strides.

Answered By - hpaulj