Return to Question

Prepare some dummy data to investigate:

alist = RandomSample[Table[ToExpression["a" <> ToString[i]], {i, 1, 10000}]];
range = Range[10000];
Do[
 len = RandomInteger[{3000, 10000}];
 select = Sort[RandomSample[range, len]];
 sublists[j] = alist[[select]];
 , {j, 1, 5000}]

we have 5000 sublists of length between 3000 and 10000 elements "ai" in a particular order. I would like to have a function that merges all 5000 sublists such that all duplicates are discarded and any "ai" appear to the left of "aj" if they do so in any of the sublists. How can one do this in Mathematica most efficiently?

A tiny example of the above would be:

alist = {a1,a3,a2,a5,a4};
sublists[1] = {a1,a5};
sublists[2] = {a3,a2,a5};
sublists[3] = {a1,a2};

so that the function merge returns:

merge[Table[sublists[i],{i,1,3}]]

{a1,a3,a2,a5}

Note that merge was not given the actual alist.

Prepare some dummy data to investigate:

alist = RandomSample[Table[ToExpression["a" <> ToString[i]], {i, 1, 10000}]];
range = Range[10000];
Do[
 len = RandomInteger[{3000, 10000}];
 select = Sort[RandomSample[range, len]];
 sublists[j] = alist[[select]];
 , {j, 1, 5000}]

we have 5000 sublists of length between 3000 and 10000 elements "ai" in a particular order. I would like to have a function that merges all 5000 sublists such that all duplicates are discarded and any "ai" appear to the left of "aj" if they do so in any of the sublists. How can one do this in Mathematica most efficiently?

A tiny example of the above would be:

alist = {a1,a3,a2,a5,a4};
sublists[1] = {a1,a5};
sublists[2] = {a3,a2,a5};
sublists[3] = {a1,a2};

so that the function merge returns:

merge[Table[sublists[i],{i,1,3}]]

{a1,a3,a2,a5}

Note that merge was not given the actual alist.

EDIT:

Investigating the Experimental'ShortestSupersequence command, let us replace the definition of alist above by

alist = Table[a[i], {i, 1, 10000}];

This creates a list of strictly increasing a[i]. Generating the sublists from this as above, we get for example

seq = Fold[Experimental`ShortestSupersequence, sublists /@ Range[5000]];
seq//Length

10984

Repeating the steps seems to consistently return a seq that is longer than 10000, while

seq // DeleteDuplicates // Length

10000

To check that all sublists contain a[i] elements in strictly increasing order, we can do:

FreeQ[
 Table[
  tmp = sublists[i] /. a[x_] -> x;
  tmp = tmp[[2 ;;]] - tmp[[;; -2]];
  FreeQ[tmp/Abs[tmp], -1]
  , {i, 1, 5000}]
 , False]

True

The only way how some of the sublists might have some elements reversed in inconsistent order with alist is if we had {...,a[i],...,a[j],...} with j<i somewhere, which is ruled out by the above test. So it seems that Experimental'ShortestSupersequence is buggy...

Prepare some dummy data to investigate:

alist = RandomSample[Table[ToExpression["a" <> ToString[i]], {i, 1, 10000}]];
range = Range[10000];
Do[
 len = RandomInteger[{3000, 10000}];
 select = Sort[RandomSample[range, len]];
 sublists[j] = alist[[select]];
 , {j, 1, 5000}]

we have 5000 sublists of length between 3000 and 10000 elements "ai" in a particular order. I would like to have a function that merges all 5000 sublists such that all duplicates are discarded and any "ai" appear to the left of "aj" if they do so in alist. For the purpose of an actual real world problem one should assume that alist is not known explicitly, but sublists[j] are known. How can one do this in Mathematica most efficiently?

A tiny example of the above would be:

alist = {a1,a3,a2,a5,a4};
sublists[1] = {a1,a5};
sublists[2] = {a3,a2,a5};
sublists[3] = {a1,a2};

so that the function merge returns:

merge[Table[sublists[i],{i,1,3}]]

{a1,a3,a2,a5}

Note that merge was not given the actual alist to compare to, but by the order of the a elements in the sublists it assables the merged list in correct order.

Prepare some dummy data to investigate:

alist = RandomSample[Table[ToExpression["a" <> ToString[i]], {i, 1, 10000}]];
range = Range[10000];
Do[
 len = RandomInteger[{3000, 10000}];
 select = Sort[RandomSample[range, len]];
 sublists[j] = alist[[select]];
 , {j, 1, 5000}]

we have 5000 sublists of length between 3000 and 10000 elements "ai" in a particular order. I would like to have a function that merges all 5000 sublists such that all duplicates are discarded and any "ai" appear to the left of "aj" if they do so in any of the sublists. How can one do this in Mathematica most efficiently?

A tiny example of the above would be:

alist = {a1,a3,a2,a5,a4};
sublists[1] = {a1,a5};
sublists[2] = {a3,a2,a5};
sublists[3] = {a1,a2};

so that the function merge returns:

merge[Table[sublists[i],{i,1,3}]]

{a1,a3,a2,a5}

Note that merge was not given the actual alist.

Prepare some dummy data to investigate:

alist = RandomSample[Table[ToExpression["a" <> ToString[i]], {i, 1, 10000}]];
range = Range[10000];
Do[
 len = RandomInteger[{3000, 10000}];
 select = Sort[RandomSample[range, len]];
 sublists[j] = alist[[select]];
 , {j, 1, 5000}]

we have 5000 sublists of length between 3000 and 10000 elements "ai" in a particular order. I would like to have a function that merges all 5000 sublists such that all duplicates are discarded and any "ai" appear to the left of "aj" if they do so in alist. For the purpose of an actual real world problem one should assume that alist is not known explicitly, but sublists[j] are known. How can one do this in Mathematica most efficiently?

Prepare some dummy data to investigate:

alist = RandomSample[Table[ToExpression["a" <> ToString[i]], {i, 1, 10000}]];
range = Range[10000];
Do[
 len = RandomInteger[{3000, 10000}];
 select = Sort[RandomSample[range, len]];
 sublists[j] = alist[[select]];
 , {j, 1, 5000}]

we have 5000 sublists of length between 3000 and 10000 elements "ai" in a particular order. I would like to have a function that merges all 5000 sublists such that all duplicates are discarded and any "ai" appear to the left of "aj" if they do so in alist. For the purpose of an actual real world problem one should assume that alist is not known explicitly, but sublists[j] are known. How can one do this in Mathematica most efficiently?

A tiny example of the above would be:

alist = {a1,a3,a2,a5,a4};
sublists[1] = {a1,a5};
sublists[2] = {a3,a2,a5};
sublists[3] = {a1,a2};

so that the function merge returns:

merge[Table[sublists[i],{i,1,3}]]

{a1,a3,a2,a5}

Note that merge was not given the actual alist to compare to, but by the order of the a elements in the sublists it assables the merged list in correct order.