2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Explain "but their order is compatible." $\endgroup$
    – David G. Stork
    Commented Aug 14 at 15:37
  • $\begingroup$ 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? $\endgroup$
    – lericr
    Commented Aug 14 at 16:02
  • $\begingroup$ 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) $\endgroup$
    – Albercoc
    Commented Aug 14 at 16:09
  • $\begingroup$ Well, we can define/discover an ordering as pairs like this: Catenate[Subsets[#, {2}] & /@ input] $\endgroup$
    – lericr
    Commented Aug 14 at 16:11
  • $\begingroup$ 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 $\endgroup$
    – Albercoc
    Commented Aug 15 at 8:57

2 Answers 2

Reset to default
7
$\begingroup$

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

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Super interesting. This works always and the theory behind is beautiful. Thank you so much $\endgroup$
    – Albercoc
    Commented Aug 15 at 8:35
3
$\begingroup$

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} *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Albercoc
    Commented Aug 14 at 16:51
  • $\begingroup$ But your solution indeed works great for the minimal example I posted, so I will accept it $\endgroup$
    – Albercoc
    Commented Aug 14 at 17:13
  • $\begingroup$ @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}. $\endgroup$
    – Domen
    Commented Aug 14 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.