Flatten command: matrix as second argument

One thing I could never wrap my head around is how Flatten works when provided with a matrix as the second argument, and the Mathematica help isn't particularly good on this one.

Taken from the Flatten Mathematica documentation:

Flatten[list, {{s11, s12, ...}, {s21, s22, ...}, ...}]


Flattens list by combining all levels $s_{ij}$ to make each level $i$ in the result.

Could someone elaborate on what this actually means/does?

-

One convenient way to think of Flatten with the second argument is that it performs something like Transpose for ragged (irregular) lists. Here is a simple example:

In[63]:=  Flatten[{{1,2,3},{4,5},{6,7},{8,9,10}},{{2},{1}}]
Out[63]= {{1,4,6,8},{2,5,7,9},{3,10}}


What happens is that elements which constituted level 1 in the original list are now constituents at level 2 in the result, and vice versa. This is exactly what Transpose does, but done for irregular lists. Note however, that some information about positions is lost here, so we can not directly inverse the operation:

In[65]:= Flatten[{{1,4,6,8},{2,5,7,9},{3,10}},{{2},{1}}]
Out[65]= {{1,2,3},{4,5,10},{6,7},{8,9}}


To have it reversed correctly, we'd have to do something like this:

In[67]:= Flatten/@Flatten[{{1,4,6,8},{2,5,7,9},{3,{},{},10}},{{2},{1}}]
Out[67]= {{1,2,3},{4,5},{6,7},{8,9,10}}


A more interesting example is when we have deeper nesting:

In[68]:= Flatten[{{{1,2,3},{4,5}},{{6,7},{8,9,10}}},{{2},{1},{3}}]
Out[68]= {{{1,2,3},{6,7}},{{4,5},{8,9,10}}}


Here again, we can see that Flatten effectively worked like (generalized) Transpose, interchanging pieces at the first 2 levels. The following will be harder to understand:

In[69]:=  Flatten[{{{1, 2, 3}, {4, 5}}, {{6, 7}, {8, 9,  10}}}, {{3}, {1}, {2}}]
Out[69]= {{{1, 4}, {6, 8}}, {{2, 5}, {7, 9}}, {{3}, {10}}}


The following image illustrates this generalized transpose:

We may do it in two consecutive steps:

In[72]:=  step1 = Flatten[{{{1,2,3},{4,5}},{{6,7},{8,9,10}}},{{1},{3},{2}}]
Out[72]= {{{1,4},{2,5},{3}},{{6,8},{7,9},{10}}}

In[73]:= step2 =  Flatten[step1,{{2},{1},{3}}]
Out[73]= {{{1,4},{6,8}},{{2,5},{7,9}},{{3},{10}}}


Since the permutation {3,1,2} can be obtained as {1,3,2} followed by {2,1,3}. Another way to see how it works is to use numbers which indicate the position in the list structure:

Flatten[{{{111, 112, 113}, {121, 122}}, {{211, 212}, {221, 222, 223}}}, {{3}, {1}, {2}}]
(*
==> {{{111, 121}, {211, 221}}, {{112, 122}, {212, 222}}, {{113}, {223}}}
*)


From this, one can see that in the outermost list (first level), the third index (corresponding the third level of the original list) grows, in each member list (second level) the first element grows per element (corresponding to the first level of the original list), and finally in the innermost (third level) lists, the second index grows, corresponding to the second level in the original list. Generally, if the k-th element of the list passed as second element is {n}, growing the k-th index in the resulting list structure corresponds to increasing the n-th index in the original structure.

Finally, one can combine several levels to effectively flatten the sub-levels, like so:

In[74]:=  Flatten[{{{1,2,3},{4,5}},{{6,7},{8,9,10}}},{{2},{1,3}}]
Out[74]= {{1,2,3,6,7},{4,5,8,9,10}}

-
I think it's easier to understand if the numbers indicate the original position in the nested list. For example, in the three-number permutation example, it would be Flatten[{{{111, 112, 113}, {121, 122}}, {{211, 212}, {{221,222,223}}}, {{3},{1},{2}}} and the result would read {{{111, 121}, {211, 221}}, {{112, 122}, {212, 222}}, {{113}, {223}}}. –  celtschk Apr 13 '12 at 10:18
@celtschk Thanks, but I am not convinced. For me personally, it is easier to track visually distinct numbers and see where they end up in the new structure. But feel free to add this to my answer, this is perfectly fine with me. –  Leonid Shifrin Apr 13 '12 at 10:55
I guess our ways of understanding are just different in that respect. Actually only after rewriting my way, I completely understood the cyclic permutation (but then directly, without the two-step decomposition you did afterward). The point is that this way, you can see immediately which index changes if you move along each list, and you can determine where the number originated in the list structure from without even looking at the original list. In other words, it more directly (at least to me) reveals the structure of the transformation. –  celtschk Apr 14 '12 at 18:39
@celtschk Yes, I understood your reasoning. But for me, it was easier to understand which elements jumped which lists, rather than look at elements' indices. May be it's just me, I always gravitated to geometry rather than algebra. I think both ways have their merits. –  Leonid Shifrin Apr 14 '12 at 19:05
OK, I've now inserted the example using index-numbers with corresponding explanation. –  celtschk Apr 14 '12 at 19:14

A second list argument to Flatten serves two purposes. First, it specifies the order in which indices will be iterated when gathering elements. Second, it describes list flattening in the final result. Let's look at each of these capabilities in turn.

Iteration Order

Consider the following matrix:

$m = Array[Subscript[m, Row[{##}]]&, {4, 3, 2}];$m // MatrixForm


We can use a Table expression to create a copy of the matrix by iterating over all of its elements:

$m === Table[$m[[i, j, k]], {i, 1, 4}, {j, 1, 3}, {k, 1, 2}]
(* True *)


This identity operation is uninteresting, but we can transform the array by swapping the order of the iteration variables. For example, we can swap i and j iterators. This amounts to swapping the level 1 and level 2 indices and their corresponding elements:

$r = Table[$m[[i, j, k]], {j, 1, 3}, {i, 1, 4}, {k, 1, 2}];
$r // MatrixForm  If we look carefully, we can see that each original element $m[[i, j, k]] will be found to correspond to the resulting element $r[[j, i, k]] -- the first two indices have been "swapped". Flatten allows us to express an equivalent operation to this Table expression more succintly: $r === Flatten[$m, {{2}, {1}, {3}}] (* True *)  The second argument of the Flatten expression explicitly specifies the desired index order: indices 1, 2, 3 are altered to become indices 2, 1, 3. Note how we did not need to specify a range for each dimension of the array -- a significant notational convenience. The following Flatten is an identity operation since it specifies no change to index order: $m === Flatten[$m, {{1}, {2}, {3}}] (* True *)  Whereas the following expression re-arranges all three indices: 1, 2, 3 -> 3, 2, 1 Flatten[$m, {{3}, {2}, {1}}] // MatrixForm


Again, we can verify that an original element found at the index [[i, j, k]] will now be found at [[k, j, i]] in the result.

If any indices are omitted from a Flatten expression, they are treated as if they had been specified last and in their natural order:

Flatten[$m, {{3}}] === Flatten[$m, {{3}, {1}, {2}}]
(* True *)


This last example can be abbreviated even further:

Flatten[$m, {3}] === Flatten[$m, {{3}}]
(* True *)


An empty index list results in the identity operation:

$m === Flatten[$m, {}] === Flatten[$m, {1}] === Flatten[$m, {{1}, {2}, {3}}]
(* True *)


That takes care of iteration order and index swapping. Now, let's look at...

List Flattening

One might wonder why we had to specify each index in a sublist in the previous examples. The reason is that each sublist in the index specification specifies which indices are to be flattened together in the result. Consider again the following identity operation:

Flatten[$m, {{1}, {2}, {3}}] // MatrixForm  What happens if we combine the first two indices into the same sublist? Flatten[$m, {{1, 2}, {3}}] // MatrixForm


We can see that the original result was a 4 x 3 grid of pairs, but the second result is a simple list of pairs. The deepest structure, the pairs, were left untouched. The first two levels have been flattened into a single level. The pairs in the third level of the source matrix remained unflattened.

We could combine the second two indices instead:

Flatten[$m, {{1}, {2, 3}}] // MatrixForm  This result has the same number of rows as the original matrix, meaning that the first level was left untouched. But each result row has a flat list of six elements taken from the corresponding original row of three pairs. Thus, the lower two levels have been flattened. We can also combine all three indices to get a completely flattened result: Flatten[$m, {{1, 2, 3}}]


This can be abbreviated:

Flatten[$m, {{1, 2, 3}}] === Flatten[$m, {1, 2, 3}] === Flatten[$m] (* True *)  Flatten also offers a shorthand notation when no index swapping is to take place: $n = Array[n[##]&, {2, 2, 2, 2, 2}];

Flatten[$n, {{1}, {2}, {3}, {4}, {5}}] === Flatten[$n, 0]
(* True *)

Flatten[$n, {{1, 2}, {3}, {4}, {5}}] === Flatten[$n, 1]
(* True *)

Flatten[$n, {{1, 2, 3}, {4}, {5}}] === Flatten[$n, 2]
(* True *)

Flatten[$n, {{1, 2, 3, 4}, {5}}] === Flatten[$n, 3]
(* True *)


"Ragged" Arrays

All of the examples so far have used matrices of various dimensions. Flatten offers a very powerful feature that makes it more than just an abbreviation for a Table expression. Flatten will gracefully handle the case where sublists at any given level have differing lengths. Missing elements will be quietly ignored. For example, a triangular array can be flipped:

$t = Array[# Range[#]&, {5}];$t // TableForm
(*
1
2   4
3   6   9
4   8   12  16
5   10  15  20  25
*)

Flatten[$t, {{2}, {1}}] // TableForm (* 1 2 3 4 5 4 6 8 10 9 12 15 16 20 25 *)  ... or flipped and flattened: Flatten[$t, {{2, 1}}]
(* {1,2,3,4,5,4,6,8,10,9,12,15,16,20,25} *)

-
This is a fantastic and thorough explanation! –  The Toad Nov 17 '12 at 17:49
@rm-rf Thanks. I figure that if Flatten were generalized to accept a function to apply when flattening (contracting) indices, that would be an excellent start to "tensor algebra in a can". –  WReach Nov 17 '12 at 17:50
Sometimes we need to do internal contractions. Now I know I can do it using Flatten[$m, {{1}, {2, 3}}] instead of Map Flatten over some level. It would be nice if Flatten accepted negative arguments to do that. So this case could be write like Flatten[$m, -2]. –  Murta Nov 17 '12 at 22:01
Why this excellent answer got less votes than Leonid's :(. –  mm.Jang Sep 17 '13 at 14:47
@Tangshutao See the second FAQ on my profile. –  WReach Sep 16 '14 at 3:11