# Producing “binary” associated lists

This is a problem for which there must be an elegant and efficient solution which eludes me. The problem is best described with an example. Suppose you have the list $$v$$ of numbers from 1 to 10 in order, and another list, let us say, $$a={5,6,8,1,3,4,7,9,2}$$ which is a random sample of the numbers from 1 to 9. We will think of this second list a set of indices that will tell us how to associate the numbers in the original list $$v$$ so as to end up with a binary list of binary sublists, like the associated arguments of some binary product, if we may so think of it that way.

The first 5 tells us we must begin by associating 5,6 in $$v$$ to get

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

Then in $$a$$ comes 6, which tells us that we must produce the new list

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

Then in $$a$$ comes 8, which tells us we must associate 8 and 9 to get

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

Then comes 1, and later 3, which tells us we must associate 1 and 2, and also 3 and 4, to get

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

Now it gets interesting, 4 comes next in $$a$$, so we must join the outermost sublist that ends with 4, and the next one:

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

Now comes 7. So we will join {{3,4},{{5,6},7}} with {8,9} in a binary list. We move on and rush a bit towards the final product. Then comes 9, which tells us to tack on 10 to the sublist ending in 9. Finally comes 2, which tells us now how to get the final result:

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

So the problem is how to associate in general, the list of $$n$$ numbers (in an application they would be variables), using a random sample of a list of $$n-1$$ numbers, as I have described in the example. I feel I would almost like a one liner to do this. I am sure there is a very effective way to do this, but I can’t quite think of what it might be at the moment.

I thought it would be easier to work through an example than try to describe what I do. Then again, I am not very good with words. If this is not clear, I will try again.

• I suspect it's going to be a Fold of some kind e.g Fold[g,Range,{5,6,8,1,3,4,7,9,2}] but g will be quite complicated. May 25 '20 at 21:45
• in an application they would be variables - what happens if the items in the list are not unique? e.g {x,x,x,y,y,z} May 26 '20 at 13:35
• @flinty indeed, they are variables .. and List is really a binary operator (Cross) but that is a bit besides the point ... you want to produce an association for the binary operator from some other information as described. The variables are all distinct in the application I have in mind. But even if they were, a list is a list, and you can still group the set of variables into sublists which are binary. I am partially there in terms of coming up with a solution to this, but it is not elegant or short ... which I feel must be possible. In any case, if I get this working, I will post it.
– EGME
May 26 '20 at 16:58
• If you intend to use this for cross products could you post that problem? It might be easier to understand in context and it's quite possible a function already exists that you're not aware of. May 26 '20 at 17:12
• @flinty It is very simple ... where you have List in the situation above, replace by Cross ... but to actually work on it, it is easier to think of lists. I am afraid that if I post another almost identical problem the moderators will close it because it is duplicated ... however, I will edit this post to show this ... I need a bit of time to do it.
– EGME
May 26 '20 at 17:16

Here is my answer to the question. I won't accept it as I believe there must be a much better way to do this. But this at least works. I also post some code that illustrates what happens when you replace List by something like Cross

We need three functions, one function which I call maxsublistlast, which finds the largest sublist which contains a given item in the last position of the flattened expression. Then we have maxsublistfirst, which finds the largest sublist which contains a given item in the first position of the flattened expression. Finally we have a function assoc which makes the association with the right number of variables (here integers, after the code I show how to replace the integers by variables, and the list association by a binary product).

 maxsublistlast[list_, item_] := Module[{a, i},
a = Position[list, item] // Flatten;
i = 1;
While[item != (list[[Sequence @@ a[[1 ;; i]]]] //
If[i < Length[a], Flatten[#], Nothing] & //
If[i < Length[a], Last[#], #] &), i = i + 1];
list[[Sequence @@ a[[1 ;; i]]]]
]

maxsublistfirst[list_, item_] := Module[{a, i},
a = Position[list, item] // Flatten;
i = 1;
While[item != (list[[Sequence @@ a[[1 ;; i]]]] //
If[i < Length[a], Flatten[#], Nothing] & //
If[i < Length[a], First[#], #] &), i = i + 1];
list[[Sequence @@ a[[1 ;; i]]]]
]

assoc[sample_] :=
Module[{alis = Range[Length[sample] + 1], l0 = sample},
Table[alis =
DeleteCases[alis, maxsublistfirst[alis, l0[[i]] + 1]] /.
maxsublistlast[alis,
l0[[i]]] -> {maxsublistlast[alis, l0[[i]]],
maxsublistfirst[alis, l0[[i]] + 1]}, {i, 1, Length[l0]}] //
Last // First
]

{{1, 2}, {{{{3, 4}, {{5, 6}, 7}}, 8, 9}, 10}};
% // maxsublistlast[#, 7] &
%% // maxsublistfirst[#, 8] &

{{3, 4}, {{5, 6}, 7}}
8

assoc[{5,6,8,1,3,4,7,9,2}]

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


Now to see how we replace the integers in the list by variables, and to apply a binary product like cross we do the following

 assoc[{5,6,8,1,3,4,7,9,2}] /. x_Integer :> ToExpression[StringJoin["x", ToString[x]]]
% /. List -> Cross

{{x1, x2}, {{{{x3, x4}, {{x5, x6}, x7}}, {x8, x9}}, x10}}

Cross[Cross[x1, x2],Cross[Cross[Cross[Cross[x3, x4],Cross[Cross[x5, x6], x7]], Cross[x8, x9]], x10]]


I am still hoping someone will show me a better, more code efficient way of doing the association. Thanks