How Can I Flatten This List with Inner List of Lists?

Given the following List

lis =
{
{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}
}


I would like to get this List:

{
{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}
}.


Flatten is not doing it for me. Note that the actual List is huge and the List of Lists contained in this list can have variable lengths as in the example above one contains 3 inner list the other contains 4.

• Are your lists only this deep or do you have additional or arbitrary layers of lists?
– rm -rf
Feb 27, 2013 at 6:44
• A simple and straightforward solution would be lis //. {h___, {x__List}, t___} :> {h, x, t}, but since your lists are huge, it'll be inefficient.
– rm -rf
Feb 27, 2013 at 6:47
• @rm-rf, the lists are only this deep. Feb 27, 2013 at 6:49

8 Answers

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).

• thanks. Your method is generally faster. Feb 27, 2013 at 8:09
• @RunnyKine Depending on the actual structure of your data there are other options and considerations, e.g. Level[lis, {-2}] should be fastest/best if the elements of your sublists are atomic. I've been distracted by another question but I'll come back to this one. In the mean time can you tell what your actual data looks like? Feb 27, 2013 at 8:44
• The actual data looks like I described above and just like your example shows except that every list is of length three except the list of lists that can have variable lengths (still the inner lists are of length 3) like the list with 4 elements and that with 3 elements in my example. Your answer definitely solves the problem. Feb 27, 2013 at 20:33

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.

• Thanks. This is definitely fast. Feb 27, 2013 at 7:09
• Maybe I read too much into the question but this doesn't work as I expect or a deeper expression, e.g. RandomChoice[lis, #] & /@ RandomInteger[{1, 7}, 10]. If I apply the function repeatedly so as to get the expected result it takes longer than Cases. Feb 27, 2013 at 7:12
• @Mr.Wizard See my comment to the OP under the question and their response
– rm -rf
Feb 27, 2013 at 7:16
• Oh. Well, aren't you the one that contends that comments are not content? :^) Feb 27, 2013 at 7:17
• @Mr.Wizard That's why I posted an answer and left the room heater solution as a comment :) I meant the other comment where the OP clarifies the depth of the lists...
– rm -rf
Feb 27, 2013 at 7:21

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}}

• Nice, you could also add Sequence -> List at the end, just in case the original list has no matrix-lists.
– rm -rf
Feb 27, 2013 at 6:50
• Nice one. +1. Thanks, I like the elegance of your answers. Feb 27, 2013 at 7:05

Yet another one (since I don't see Replace mentioned):

Replace[lis, {l__List} -> l, {1}]

(* {{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}} *)


On my machine this is about three times faster than @rm's solution for his first dataset and a little bit faster for the second. Replace can be surprising ;-) I learned about its speed here.

• Nice. +1 for the Replace tip. Mar 1, 2013 at 1:30

How about:

Partition[Flatten[lis], 3]

• The question states: "Note that the actual List is huge and the List of Lists contained in this list can have variable lengths." Feb 27, 2013 at 10:18
• ok, I read the question as the "list of lists" could have variable lengths as opposed to the lists within the "list of lists". The description isn't not totally unclear to me still.
– Iiss
Feb 27, 2013 at 10:44
Cases[lis, __?VectorQ, -2]


{{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}}

Yet another solution

flatten[l_List] := Block[{aux}, aux[x_List] := x //. List[a__List] :> Sequence@a; aux /@ l]

• I gave a solution based on //. in the comments, but didn't post it because the OP mentioned that their lists are huge and //. will be terribly slow
– rm -rf
Feb 27, 2013 at 15:06
list =
{{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}};

FlattenAt[list, Position[list, _?MatrixQ]]


{{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}}