How can I Flatten this List with Inner List of Lists?

Starting with (notice lists of length 1, 2, 3, and 4):

lis = {{1, 2, 3, 4}, {3, 2, 3}, {{3, 7, 5}, {7}, {6, 2, 1}}, {3, 2, 7},
       {{3, 3, 5}, {7, 7, 8, 0}, {9, 4, 2}, {9, 0, 0}}, {8, 5, 4}, {7, 4}};

You could simply do:

Level[lis, {-2}]
{{1, 2, 3, 4}, {3, 2, 3}, {3, 7, 5}, {7}, {6, 2, 1}, {3, 2, 7},
 {3, 3, 5}, {7, 7, 8, 0}, {9, 4, 2}, {9, 0, 0}, {8, 5, 4}, {7, 4}}

This assumes that the elements of your sub-lists are atomic, i.e. Depth 1, such as head Integer, Read, String, etc.

If your elements are not atomic then a different method will be needed but I will need to better understand the possible forms of your data structure. For example could you ever have something like {6, {2, 3}, 1} in your list, and what should be done with it?

One option is Cases with a pattern for objects that are not to be flattened:

Cases[lis, {Except[_List] ..}, -2]

Another is a recursive function similar to what rm-rf shows (but extensible to more deeply nested expressions).


Here's another alternative which should be faster than using ?MatrixQ and Sequence@@ for large lists.

Block[{f},
     f[{x__List}] := x;
     f[x_] := x;
     f /@ list
]

Timings:

Large list with relatively few sublists of array depth 2

list = With[{r := RandomInteger[{1, 10}]}, 
    Table[RandomInteger[{0, 9}, {r, r}], {1000}] ~Join~
    Table[RandomInteger[{0, 9}, {r}], {1000000}]];

AbsoluteTiming[out1 = list /. x_?MatrixQ :> Sequence @@ x;] (* Verbeia *)
(* {4.213474, Null} *)

AbsoluteTiming[
    out2 = Block[{f},
        f[{x__List}] := x;
        f[x_] := x;
        f /@ list
    ];
] (* rm -rf *)
(* {0.818107, Null} *)

AbsoluteTiming[out3 = Cases[list, {__Integer}, -2];] (* Mr.Wizard *)
(* {0.884933, Null} *)

out3 == out2 == out3
(* True *)

Large list with same number of sublists of depth 1 and 2.

list = With[{r := RandomInteger[{1, 10}]}, 
    Table[RandomInteger[{0, 9}, {r, r}], {1000000}] ~Join~
    Table[RandomInteger[{0, 9}, {r}], {1000000}]
];

The timings are (in the same order)

(* {38.116132, 17.419978, 6.152006} *)

Large list with relatively few sublists of array depth 1

list = With[{r := RandomInteger[{1, 10}]}, 
    Table[RandomInteger[{0, 9}, {r, r}], {10000000}] ~Join~
    Table[RandomInteger[{0, 9}, {r}], {1000}]
];

Timings are

(* {14.443210, 6.843764, 4.206555 *)

So it seems that the size and structure of the list also matters for the timings, with mine tending to be faster when there are relatively few sublists of depth 2 (since the main workhorse is just f[x_] := x) and Mr.Wizard's faster when the situation is the opposite. However, Mr.Wizard's is in general a much faster alternative and applicable to lists of arbitrary depth.


You could try

lis /. a_?MatrixQ :> Sequence @@ a
{{1, 2, 3}, {3, 2, 3}, {3, 7, 5}, {7, 5, 3}, {6, 2, 1}, {3, 2, 7}, {3,
  3, 5}, {7, 7, 8}, {9, 4, 2}, {9, 0, 0}, {8, 5, 4}, {7, 4, 3}}

This is a bit of a hack, but if you had unknown depth of nesting, you could try something like:

lis2 = {{1, 2, 3}, {3, 2, 3}, {{{3, 7, 5}, {7, 5, 3}, {6, 2, 1}}}, {3,
    2, 7}, {{3, 3, 5}, {7, 7, 8}, {9, 4, 2}, {9, 0, 0}}, {8, 5, 4}, {7, 4, 3}}

Last@DeleteCases[
  FixedPointList[# /. a_?MatrixQ :> Sequence @@ a &, lis2], _?VectorQ]

The reason I do it this way instead of using ReplaceRepeated (//.) is that the final desired outcome is itself a matrix, and is matched by the rule. So the end point is a Sequence of vectors. You want to get to that point, eliminate those vectors from the results, and then pick whatever was the result of the FixedPointList before that happened. You can see this by just using FixedPointList, which gives the following output:

{{{1, 2, 3}, {3, 2, 3}, {{{3, 7, 5}, {7, 5, 3}, {6, 2, 1}}}, {3, 2, 
   7}, {{3, 3, 5}, {7, 7, 8}, {9, 4, 2}, {9, 0, 0}}, {8, 5, 4}, {7, 4,
    3}}, {{1, 2, 3}, {3, 2, 3}, {{3, 7, 5}, {7, 5, 3}, {6, 2, 1}}, {3,
    2, 7}, {3, 3, 5}, {7, 7, 8}, {9, 4, 2}, {9, 0, 0}, {8, 5, 4}, {7, 
   4, 3}}, {{1, 2, 3}, {3, 2, 3}, {3, 7, 5}, {7, 5, 3}, {6, 2, 1}, {3,
    2, 7}, {3, 3, 5}, {7, 7, 8}, {9, 4, 2}, {9, 0, 0}, {8, 5, 4}, {7, 
   4, 3}}, {1, 2, 3}, {3, 2, 3}, {3, 7, 5}, {7, 5, 3}, {6, 2, 1}, {3, 
  2, 7}, {3, 3, 5}, {7, 7, 8}, {9, 4, 2}, {9, 0, 0}, {8, 5, 4}, {7, 4,
   3}, {1, 2, 3}, {1, 2, 3}}