# How can I create an Association from a multidimensional list of values and a list of keys?

Given a list of values such as

vals = {{{{0., 633.25}, {642.96, 677.34}}, {{591.56, 632.45}, {634.9, 715.6}}}}


and a list of "Dimensions" such as

dims = {{"New York City"}, {"Terrace house", "Apartment"}, {"Two bed", "Three bed"}, {"2016", "2017"}}


how can I create the Association (I suppose really a tree)

<|"New York City" ->
<|"Terrace House" ->
<|"Two Bed" ->
<|"2016" -> 0.,
"2017" -> 633.25|>,
"Three Bed" ->
<|"2016" -> 642.96,
"2017" -> 677.34|>|>,
"Apartment" ->
<|"Two Bed" ->
<|"2016" -> 591.56,
"2017" -> 632.45|>,
"Three Bed" ->
<|"2016" -> 634.9,
"2017" -> 715.6|>|>|>|>


You can see that each level in vals is a level in the tree - the innermost level is dims[[4]] (2016 or 2017), the next level up is dims[[3]] (two bed or three bed), next is dims[[2]] (terraced house or apartment), and finally the topmost level is dims[[1]], New York City.

I have attempted a few different approaches here, but I think my understanding of how Levels work is lacking here.

My best attempt so far is the following:

Table[
MapIndexed[
dims[[lvl, Last[#2]]] -> # &, vals, {lvl}],
{lvl, Length@Dimensions[vals]}]


The output from this is:

{{"New York City" -> {{{0., 633.25}, {642.96, 677.34}}, {{591.56, 632.45}, {634.9, 715.6}}}},
{{"Terrace house" -> {{0., 633.25}, {642.96, 677.34}},
"Apartment" -> {{591.56, 632.45}, {634.9, 715.6}}}},
{{{"Two bed" -> {0., 633.25},
"Three bed" -> {642.96, 677.34}},
{"Two bed" -> {591.56, 632.45},
"Three bed" -> {634.9, 715.6}}}},
{{{{"2016" -> 0., "2017" -> 633.25},
{"2016" -> 642.96, "2017" -> 677.34}},
{{"2016" -> 591.56, "2017" -> 632.45},
{"2016" -> 634.9, "2017" -> 715.6}}}}}


Which is sort of close, but not correct.

My solution would ideally scale to dimensions and values of any size - not just one or two dimensional data (another city, for instance, or a hundred years, or both, and also more house sizes, and so on).

I'm sure the correct answer here is a recursive function, and I'm sure it's not even that hard, I'm just not thinking about it correctly!

Thanks for your help.

Edit:

I have done a little more exploration and have gotten a little bit closer using Nest.

Module[{i = 0, d = Reverse[dims]},
Nest[(i++;
Partition[
Riffle[#, d[[i]], {1, -2, 2}],
Length[d[[i]]]]) &,
Flatten[vals], 3]]


This gives me

{{"Terrace house", {"Two bed", {"2016", 0.}}},
{"Apartment", {"Three bed", {"2017", 633.25}}},
{"Terrace house", {"Two bed", {"2016", 642.96}}},
{"Apartment", {"Three bed", {"2017", 677.34}}},
{"Terrace house", {"Two bed", {"2016", 591.56}}},
{"Apartment", {"Three bed", {"2017",  632.45}}},
{"Terrace house", {"Two bed", {"2016", 634.9}}},
{"Apartment", {"Three bed", {"2017", 715.6}}}}


This is getting pretty close! However, applying it an extra time (changing 3 to 4 in the Nest) gives me the following:

{{"New York City"}, {{"Terrace house", {"Two bed", {"2016", 0.}}},
{"New York City"}, {{"Apartment", {"Three bed", {"2017", 633.25}}}},
{"New York City"}, {{"Terrace house", {"Two bed", {"2016", 642.96}}}},
{"New York City"}, {{"Apartment", {"Three bed", {"2017", 677.34}}}},
{"New York City"}, {{"Terrace house", {"Two bed", {"2016", 591.56}}}},
{"New York City"}, {{"Apartment", {"Three bed", {"2017", 632.45}}}},
{"New York City"}, {{"Terrace house", {"Two bed", {"2016", 634.9}}}},
{"New York City"}, {{"Apartment", {"Three bed", {"2017", 715.6}}}}}


Close, but not right, yet.

## 4 Answers

Clear[helper];
helper[tl_] := GroupBy[tl, First -> Rest, helper];
helper[{{n_}}] := n;
helper@Transpose@Append[Flatten@vals]@Transpose@Tuples[dims]


The idea is to build a list of paths to each leaf, then use a recursive GroupBy build the association tree from the list.

## Update

I have managed to come up with something faster. But the code becomes more ugly.

Clear[fvals, i, maketree];
fvals = Flatten[vals, Depth[vals] - 3];
maketree[{first_, rest__}] :=
AssociationThread[first -> Table[maketree[{rest}], Length@first]];
maketree[{first_}] := AssociationThread[first, fvals[[i++]]];

i = 1; maketree[dims]
(*<|"New York City" -> <|"Terrace house" -> <|"Two bed" -> <|"2016" ->
0., "2017" -> 633.25|>,
"Three bed" -> <|"2016" -> 642.96, "2017" -> 677.34|>|>,
"Apartment" -> <|"Two bed" -> <|"2016" -> 591.56,
"2017" -> 632.45|>,
"Three bed" -> <|"2016" -> 634.9, "2017" -> 715.6|>|>|>|>*)


I made some timing experiments on code available. (1000 times, repeated timing).

My previous: 0.0665s

My current: 0.019s

Kuba: 0.0400s

andre: 0.0299s

Anton: 0.307s

• Great! Much shorter than my answer. Note that using the trie interpretation adheres to "the idea is to build a list of paths to each leaf[...]". Apr 14, 2018 at 15:32
• Perfect, thank you very much. That's the graceful mathematica way I was expecting! Apr 14, 2018 at 15:33
• Would you be able to give me some tips on how to optimise this a little? I have a larger test case (about 4MB of data - a few hundred dimensions and about three hundred thousand values). I've been looking in the workbench and it seems like the recursion here is causing the function to be called many many times and take a very long time. I don't see how to improve the GroupBy here - any thoughts? Apr 15, 2018 at 19:47
• @CarlLange Sorry, just saw it. My code here sacrifices performance for elegance, and is intended only for small datasets. In my experience this is a common problem in MMA coding. My first step expands to show every path in a separate list, this is creating a lot of duplicated information just for input of GroupBy. And when GroupBy is called recursively, it is doing duplicated grouping for each pair (although they have identical set of keys). My idea is to create the tree recursively directly without flattening and grouping. By the way, did you try others' code to see if they're faster? Apr 16, 2018 at 16:35
• @CarlLange I have updated the code Apr 16, 2018 at 17:11

Assuming vals has depth corresponding to dims length:

Module[{i = -2}
, Fold[
Function[{val, dim}, Map[AssociationThread[dim -> #] &, val, {i--}]]
, vals
, Reverse @ dims
]
]

<|"New York City" -> <|"Terrace house" -> <|"Two bed" -> <|"2016" ->
0., "2017" -> 633.25|>,
"Three bed" -> <|"2016" -> 642.96, "2017" -> 677.34|>|>,
"Apartment" -> <|"Two bed" -> <|"2016" -> 591.56,
"2017" -> 632.45|>,
"Three bed" -> <|"2016" -> 634.9, "2017" -> 715.6|>|>|>|>

• Thank you, this is close to the answer I was approaching! Apr 14, 2018 at 15:56

Here is a basic approach without explicit recursion :

vals = {{{{0., 633.25}, {642.96, 677.34}}, {{591.56, 632.45}, {634.9,
715.6}}}}
dims = {{"New York City"}, {"Terrace house", "Apartment"},
{"Two bed", "Three bed"}, {"2016", "2017"}}

MapIndexed[dims[[Length[#2],Last[#2]]]->#1&,vals,{1,-1}] /. x:{_Rule ...} :> Association[x]


Looking at the answer of @happyfish the code below is an overkill...

Here we find the positions corresponding in the values:

pos = Position[vals, _?NumberQ, \[Infinity]]


Here we find the dimensions corresponding to the positions:

posToDims = MapThread[Part, {dims, #}] & /@ pos


Here we make Trie records from the dimensions and the values:

t = MapThread[
Function[{d, p}, Append[d, vals[[Sequence @@ p]]]], {posToDims, pos}, 1]


Here we make the trie:

res = makeTreeAssoc[t]


Finally, we remove the redundant <|{}->{}|> (coming from Shifrin's original implementation):

res /. <|k_ -> <|{} -> {}|>|> :> k

(* {"New York City" -> <|"Terrace house" -> <|"Two bed" -> \
<|"2016" -> 0., "2017" -> 633.25|>,
"Three bed" -> <|"2016" -> 642.96, "2017" -> 677.34|>|>,
"Apartment" -> <|"Two bed" -> <|"2016" -> 591.56,
"2017" -> 632.45|>,
"Three bed" -> <|"2016" -> 634.9, "2017" -> 715.6|>|>|>} *)


## Definitions

Here is a small change of the original definitions are given in this answer:

ClearAll[makeTreeAssoc];
makeTreeAssoc[wrds_ /; MemberQ[wrds, {}]] :=
Prepend[makeTreeAssoc[DeleteCases[wrds, {}]], {} -> {}];
makeTreeAssoc[wrds_] :=
Reap[If[# =!= {}, Sow[Rest[#], First@#]] & /@
wrds, _, #1 -> Association@makeTreeAssoc[#2] &][[2]]


(I was tempted to give an answer with one of my Trie packages, but luckily Leonid Shifrin has provided a concise implementation of Tries using core Association functionalities.)

• I've accepted the other answer but this helped a lot in my understanding of how it worked. Thanks a lot! Apr 14, 2018 at 15:34
• @CarlLange Yeah, the two answers are based on the same idea. Good luck! Apr 14, 2018 at 15:37