# How to check if two nested lists have the same structure?

How can I check if nested lists like these have the same structure:

list1={ { p[x],    p[y]    } , { p[x]    } , { p[x]   , p[y]   , p[z]   , d[z^2] } }

list2={ { {1,2,0}, {3,0,0} } , { {0,0,0} } , { {1,0,1}, {0,1,0}, {1,1,1}, {0,0,1} } }


So I want to check, that there is a 3-tuple for each entry in list 1.

• Dimensions[list1]; Dimensions[list2] says the dimensions is the same. – Nasser Mar 31 '15 at 16:37
• @Nasser But Dimensions returns {3} for each list. So if I add in list1 a p[z] into the second sublist Dimensions still says they are equal. – NOhs Mar 31 '15 at 16:42
• You could compare listN/. x_ /; Head[x] =!= List :> 0 – Dr. belisarius Mar 31 '15 at 16:46
• I actually do not understand the question. But if you want to look into each dimensions itself, you can do Dimensions[list2[]] and so on. Mathematica sees each list as having 3 lists in it. But each list itself can also have other lists inside it. and so on. – Nasser Mar 31 '15 at 16:46
• I believe this question is a duplicate or at least a version of an earlier one. Can anyone recall? – Mr.Wizard Mar 31 '15 at 17:47

This can be done reasonably quickly with Position. First, we get the positions of p or d within list1:

pos1 = Position[list1, _p | _d]
(* {{1, 1}, {1, 2}, {2, 1}, {3, 1}, {3, 2}, {3, 3}, {3, 4}} *)


then we do the equivalent thing for list2:

pos2 = Position[list2, {_?NumericQ, _, _}]
(* {{1, 1}, {1, 2}, {2, 1}, {3, 1}, {3, 2}, {3, 3}, {3, 4}} *)


A quick visual inspection reveals that the lists are the same, but they can easily be tested programmatically, too.

If you want a partial match, i.e. you wish to match p only, then pos1 is only going to contain a subset of pos2, e.g.

pos3 = Position[list1, _p]
(* {{1, 1}, {1, 2}, {2, 1}, {3, 1}, {3, 2}, {3, 3}} *)


Then, to determine whether there is a triplet at these positions in list2, we use Complement

Complement[pos3, pos2]
(* {} *)


which returns all elements present in pos3 not in pos2.

• Could this be modified to allow for non numerical expressions in the 3-tuples? Basically my only concern is that all braces are correct. However, if this 3-tuple cotains {1,2,3} or {a,b,c} is irrelevant since I only want to check some obvious input errors by the user, if he later assigns a list to a I do not care. – NOhs Apr 1 '15 at 11:00
• @MrZ yes that's possible. I specialized it to numerical triples so that Position did not try to be overly inclusive, and that will be the ultimate issue with any pattern based system. But, this works as the triple pattern: a : {_, _, _} /; AllTrue[a, FreeQ[#, List] &] . However, I can imagine cases where it won't, so tweak it as needed. – rcollyer Apr 1 '15 at 12:21

It could surely be done better:

list1 = {{p[x], p[y]}, {p[x]}, {p[x], p[y], p[z], d[z^2]}};

list2 = {{{1, 2, 0}, {3, 0, 0}}, {{0, 0, 0}}, {{1, 0, 1}, {0, 1, 0}, {1, 1, 1}, {0, 0, 1}}};
Map[Dimensions, list1, Infinity] == Map[Dimensions, list2, Infinity]

(* False*)

p[_] := {a, a, a}
d[_] := {b, b, b}
Map[Dimensions, list1, Infinity] == Map[Dimensions, list2, Infinity]
(* True*)

• But now p[x] will be interpreted as {a,a,a} in my entire notebook. Can this definition be done somewhat temporarily? ClearAll[p] doesn't seem to do the trick. – NOhs Apr 1 '15 at 11:08
• @MrZ You should use your own definitions for p[x_] and d[x_].Mine were only examples – Dr. belisarius Apr 1 '15 at 11:45

Yet another possibility:

test[a_List, b_List] /; Length[a] === Length[b] := And @@ MapThread[test, {a, b}]
test[_p | _d, {_, _, _}] = True;
test[_, _] = False;


Now:

test[list1, list2]


True

This has the advantage of (partial) early exit behavior unlike Position which will scan the entirety of both expressions even if the first term differs.

To improve the early-exit behavior here is a variation with AllTrue:

ClearAll[test]

test[a_, b_] := test[{a, b}]

test[{a_List, b_List}] /; Length[a] === Length[b] :=
AllTrue[{a, b}\[Transpose], test]
test[{_p | _d, {_, _, _}}] = True;
test[{_, _}] = False;

• While that works for user's data (and hence the +1), it doesn't work more generally. Try list1a = {{p[x], p[y]}, {p[x]}, {p[x], {p[y]}, p[z], d[z^2]}} and list2a = {{{1, 2, 0}, {3, 0, 0}}, {{0, 0, 0}}, {{1, 0, 1}, {{0, 1, 0}}, {1, 1, 1}, {0, 0, 1}}}. – rcollyer Mar 31 '15 at 18:06
• @rcollyer Are you referring to the code with Inner or the correction with MapThread? – Mr.Wizard Mar 31 '15 at 18:09
• Inner. I missed the correction which works well. Carry on. :P – rcollyer Mar 31 '15 at 18:10
• @rcollyer I always appreciate the help checking my work. I voted for yours too by the way. I included an update that should be somewhat more efficient but it is not as clean as I would like. I may return to this later. – Mr.Wizard Mar 31 '15 at 18:36
• Not an issue. I thought I had you, I was wrong. :D Truthfully, I was answering the user's question per the title, not just the text, and I was seeing if your's worked as well. I was surprised that you hadn't set it up so that it would work generally, and then I found out differently. – rcollyer Mar 31 '15 at 20:10

I suppose one could use Pick, which checks that the List structure of the second argument maps onto the structure of the first:

matchShapeQ[e1_, e2_] := Quiet@Check[
Pick[e1, e2 /. Except[_List | List] -> True]; True,
False,
Pick::incomp]

matchShapeQ[list2, list1]
(*  True  *)


If a symmetric check is desired, then check both directions:

matchShapeQ[list2, list1] && matchShapeQ[list1, list2]


If matching a 3-tuple is required, perhaps

Quiet@Check[
Pick[list2, list1 /. Except[_List | List] -> {#, #, #}, #] &@ Unique[]; True,
False,
Pick::incomp]


If the 3-tuples are to have three numeric entries, then it is not strictly a structural issue, but depends on matching the type of the entries. Pick may not be a suitable tool in this localized case.

• Doesn't your second method yield true even for this list2: list2 = {{{1, 2, 0}, {3, c, 0}}, {{0, {0, 0}, 0}}, {{1, 0, 1}, {0, 1, 0}, {1, 1, 1}, {0, 0, 1}}} – NOhs Apr 1 '15 at 10:41
• @MrZ Yes, because the sub-lists at the corresponding levels have three entries. – Michael E2 Apr 1 '15 at 13:01

you can try some thing like this:

comp[n_] :=
DeleteCases[list1, _, {n, -1}] === DeleteCases[list2, _, {n, -1}]


But you have to define the level at which you want to compare the similarity down to

comp
(*True*)


Just for goofiness:

sameStruct[list1_, list2_] :=
Quiet[MapAll[0 ## &, list1] /. Indeterminate -> 0] ===
Quiet[MapAll[0 ## &, list2] /. Indeterminate -> 0];

• When I try your method it returns false for the above lists. – NOhs Apr 1 '15 at 10:44