# Union of lists with original order

I would like to combine a few lists such that the resulting list follows the order of the original lists, which will have disjoint elements, but their order is compatible.

input = {{a,C,2},{b,C},{a,b},{b,2,z},{2}}
output = {a,b,C,2,z}


I thought of //Flatten//DeleteDuplicates//SortBy[#,orderBasedOnInput]&  without success.

Any comment would be much appreciated.

• Explain "but their order is compatible." Commented Aug 14 at 15:37
• Is that ordering pre-defined somewhere? I.e. can we use it to sort the final output or do we need to infer the ordering from the inputs? Commented Aug 14 at 16:02
• That was exactly the problem. I do not have access to the original sorting function... (that was applied over each list before: that is what I meant by compatible) Commented Aug 14 at 16:09
• Well, we can define/discover an ordering as pairs like this: Catenate[Subsets[#, {2}] & /@ input] Commented Aug 14 at 16:11
• After having a look at @andre314 answer, "compatible order" apparently meant that the graph resulting from connecting subsequent elements of each list is an AcyclicGraphQ Commented Aug 15 at 8:57

Here is an approach that uses Graph and TopologicalSort :

input = {{a, C, 2}, {b, C}, {a, b}, {b, 2, z}, {2}}

(Partition[#, 2, 1] & /@ input) //
Flatten[#, 1] & //
(Apply[Rule, #] & /@ # &) //
Graph[#, VertexLabels -> Automatic] & //
TopologicalSort


{a, b, C, 2, z}

Here is what happening when the inputs are not consistent :

input = {{a, b}, {b, c}, {c, a}};

Partition[#, 2, 1] & /@ input //
Flatten[#, 1] & //
(Apply[Rule, #] & /@ # &) //
Graph[#, VertexLabels -> Automatic] & //
TopologicalSort


• Super interesting. This works always and the theory behind is beautiful. Thank you so much Commented Aug 15 at 8:35

Assuming you have a consistent and unambiguously defined order throughout your lists, you can use use Sort with a custom ordering function. This ordering function looks through your initial lists and for each pair of elements determine their correct order from a list in which both elements are present.

lists = {{a, C, 2}, {b, C}, {a, b}, {b, 2, z}, {2}};

ordering[lists_][x_, y_] :=
FirstCase[lists,
list_ /; ContainsAll[list, {x, y}] :>
First@Sign[FirstPosition[list, y] - FirstPosition[list, x]], False]

Sort[DeleteDuplicates[Flatten[lists]], ordering[lists]]
(* {a, b, C, 2, z} *)

• Thanks! Adding the list {1,2} at the end returns {a, b, C, 2, z, 1}. In the flattened list, the last two elements are z and 1, and they do not appear together in any list. Commented Aug 14 at 16:51
• But your solution indeed works great for the minimal example I posted, so I will accept it Commented Aug 14 at 17:13
• @Albercocm, sorry, I didn't properly account for such cases. Now I've added that ordering returns False if the two elements are not found together, so now the result is {1, a, b, z, C, 2}. Commented Aug 14 at 17:34