# Aligning two lists

I have two lists, L1 and L2, each with a key and some data. Let us say the key is a person's name, a string, and the data follows. (To respond to rasher's query:) Let us also assume the lists are sorted by key:

L1 = {
{"Joseph O'Rourke", data1, data2, ... },
...
}


I would like to "align" the two lists in the following sense. If L1 has a name A that is not in L2, then L2 is padded to include a "blank" record for A. And vice versa: If L2 has a name B that is not in L1, then L1 is modified to include a "blank" record for B. Then I will have two lists that "align":

L1' = { {A,...}, {0,...}, {C,...},  {D,...}, ...}
L2' = { {A,...}, {B,...}, {0,...},  {D,...}, ...}


where maybe 0 == {}. With the lists aligned in this fashion, I could make a two-column table (one column per list) that would directly compare one list against the other. My question is:

What is a clean method for accepting L1 and L2 as input, and returning L1' and L2' as output, with the latter two lists aligned as above?

I can accomplish this via tedious list For-loops, but I suspect the cognoscenti :-) will offer more concise and efficient methods. Thanks for your help!

-
something like SequenceAlignment["ABCDEG", "ABDEFG"]? – Dr. belisarius Jun 2 '14 at 0:37
Are the lists already sorted by key, and if not, if the results are sorted by key is that acceptable? – ciao Jun 2 '14 at 0:39
@rasher: Yes, let's assume the lists are already sorted by key. – Joseph O'Rourke Jun 2 '14 at 0:50
@belisarius: Yes! I was ignorant of SequenceAlignment[]. – Joseph O'Rourke Jun 2 '14 at 0:51
Related: (11746), (29164) – Mr.Wizard Jun 2 '14 at 4:03

I'm late to the party but I like this kind of problem so I'm going to answer anyway.

I propose this:

f1[a_List, b_List, fill_: {0, {}}] :=
With[{all = a ⋃ b},
Replace[
Join[all, #] ~GatherBy~ First,
{{_} -> fill, {__, x_} :> x},
1
] & /@ {a, b}
]


Test:

a = {{1, 7}, {3, 7}, {5, 2}, {8, 7}};
b = {{3, 1}, {6, 6}, {8, 7}, {9, 3}};

f1[a, b] // Grid


$\begin{array}{cccccc} \{1,7\} & \{3,7\} & \{5,2\} & \{0,\{\}\} & \{8,7\} & \{0,\{\}\} \\ \{0,\{\}\} & \{3,1\} & \{0,\{\}\} & \{6,6\} & \{8,7\} & \{9,3\} \end{array}$

Note that this sample includes keys with both identical ({8, 7}) and divergent ({3, 7}, {3, 1}) data.

-
+1, clean and pretty fast. And just elegant, as always. – ciao Jun 2 '14 at 8:31
Nice! Could you (or someone) please explain ~GatherBy~, especially the tildas. Thanks! – Joseph O'Rourke Jun 2 '14 at 10:35
@JosephO'Rourke x ~ f ~ y is equivalent to f[x,y]. It's called "Infix notation" – Dr. belisarius Jun 2 '14 at 12:10
@rasher Thanks. Since you like (at least some aspect of) my style, would you mind me refactoring the code in your answer to reduce duplication? Not only would that make it shorter, but IMO it would be clearer too, as the differences from one line to the next would be directly apparent as arguments. – Mr.Wizard Jun 2 '14 at 20:48
@Joseph After gathering the elements: a list with a single occurrence, which is matched by the pattern {_}, represents a missing key in the list under operation and needs to be replaced with the fill expression (provided as an optional argument with a default value). A list with multiple occurrences, matched by the pattern {__, x_}, represents a present key, and we want the last element gathered (matched by x_) because it came from the list under operation. If this is still not clear, or you are having trouble understanding the patterns themselves, let me know and I'll try again. – Mr.Wizard Jun 3 '14 at 1:29

If the lists are long (several hundred or more), Alternatives will get to be slow. Here's another way that will be faster on longer lists:

align[list1_, list2_] := Module[{base, replace1, replace2},
base = Union[First /@ list1, First /@ list2];
With[{arg = First[#]}, replace1[arg] = #] & /@ list1;
replace1[_] = {0, {}};
With[{arg = First[#]}, replace2[arg] = #] & /@ list2;
replace2[_] = {0, {}};
{replace1 /@ base, replace2 /@ base}


Example:

data = {"that", "natural", "cowards", "delay", "country", "himself",
"my", "will", "cast", "office", "native", "is", "awry", "s", "ay"};

l1 = {#, ToCharacterCode[#]} & /@ Sort@RandomSample[data, 10]
l2 = {#, {StringLength[#]}} & /@ Sort@RandomSample[data, 10]
(*
{{"ay", {97, 121}}, {"cast", {99, 97, 115, 116}},
{"cowards", {99, 111, 119, 97, 114, 100, 115}}, {"delay", {100, 101, 108, 97, 121}},
{"himself", {104, 105, 109, 115, 101, 108, 102}}, {"is", {105, 115}},
{"my", {109, 121}}, {"native", {110, 97, 116, 105, 118, 101}},
{"that", {116, 104, 97, 116}}, {"will", {119, 105, 108, 108}}}

{{"cast", {4}}, {"cowards", {7}}, {"delay", {5}}, {"is", {2}}, {"my", {2}},
{"native", {6}},{"natural", {7}}, {"s", {1}}, {"that", {4}}, {"will", {4}}}
*)

align[l1, l2];
Grid[Transpose@{newl1, newl2}]


-
+1, and we both over-thought it (within apparent constraints of data in OP) - see my update. – ciao Jun 2 '14 at 5:29