4
$\begingroup$

I have a large list of uniform-length lists. What is an efficient way to delete component lists that contain duplicates? For three-item sub-lists, I have used the following code:

allUnique = DeleteCases[DeleteCases[DeleteCases[listOfThreeItemLists,
  {y_,x_,x_}],{x_,y_,x_}],{x_,x_,y_}];

But enumerating all possible pairs for sub-lists of, say, seven items, seems unwieldy. Thoughts?

$\endgroup$
  • 4
    $\begingroup$ Select[listOfThreeItemLists, Signature[#] != 0 &]? $\endgroup$ – J. M. is away Oct 16 '18 at 18:58
  • 5
    $\begingroup$ Select[listOfThreeItemLists, DuplicateFreeQ]? $\endgroup$ – Henrik Schumacher Oct 16 '18 at 19:01
3
$\begingroup$
SeedRandom[1]
listOfThreeItemLists = RandomInteger[5, {10, 3}]

{{4, 2, 4}, {0, 1, 0}, {0, 2, 0}, {0, 3, 5}, {2, 0, 3}, {4, 4, 1}, {3, 3, 4}, {1, 4, 2}, {1, 1, 4}, {5, 4, 5}}

In addition to Select suggested in comments, you can also use:

DeleteCases[listOfThreeItemLists, {___, x_, ___, x_, ___}]
DeleteCases[listOfThreeItemLists, Except[_?DuplicateFreeQ]]
DeleteCases[listOfThreeItemLists, _?(Not[DuplicateFreeQ @ #] &)]
Cases[listOfThreeItemLists, _?DuplicateFreeQ]
Pick[#, DuplicateFreeQ /@ #] & @ listOfThreeItemLists

all give

{{0, 3, 5}, {2, 0, 3}, {1, 4, 2}}

$\endgroup$
  • $\begingroup$ Thank you! Because this is going to be used in a class where Mathematica is a tool, but not the focus of the class, I'm going with the top item here, which looks the easiest to explain to students. $\endgroup$ – Kevin Ausman Oct 18 '18 at 19:33
  • $\begingroup$ @KevinAusman, my pleasure. Thank you for the accept. $\endgroup$ – kglr Oct 18 '18 at 19:34
3
$\begingroup$

You can also use a bit of linear algebra to make this really fast.

Let's start with an input data set

SeedRandom[1]
n = 1000000;
m = 3;
data = RandomInteger[10, {n, m}];

Here the timing of a Select-based approach:

a = Select[data, DuplicateFreeQ]; // RepeatedTiming // First

0.68

And here a variant based on linear algebra

b = With[{
      A =  Normal[IncidenceMatrix[DirectedEdge @@@ Subsets[Range[m], {2}]]],
      u = ConstantArray[1, Binomial[m, 2]]
      },
     Pick[
      data,
      Unitize[data.A].u,
      Binomial[m, 2]
      ]
     ]; // RepeatedTiming // First

a == b

0.050

True

How does this work? Well, for a vector v of length m, the vector v.A contains all differences of elements in v. Unitize[v.A] will replace all nonzero entries with 1. Since u is a vector of ones, Unitize[v.A].u counts the number of pairs of elements in v that are duplicate-free. We can do that for all vectors in the list data at once with Unitize[data.A].u. This way we utilize than matrix-matrix and matrix-vector multiplications are highly optimized on the machine level and that Unitize is also a vectorized (thus highly efficient) function on packed arrays. In the end, we use Pick to pick only those vectors from data that contain a maximal number of duplicate-free pairs (the maximal number is Binomial[m, 2]).

This works also for larger m but the performance boost in comparison to Select+DuplicateFreeQ will decay quite qickly; starting with m = 10, Select+DuplicateFreeQ is faster on my machine. Some reasons for this are that the size of the matrix A grows quadratically in m and that DuplicateFreeQ can short-circuit when it finds the fist duplicate in a vector. Morever, there is potential to use a binary search tree for the implementation of DuplicateFreeQ so that DuplicateFreeQ might have runtime $O(m \log(m))$ instead of $m^2$...

$\endgroup$
1
$\begingroup$
nonduplist[list_?MatrixQ] := Extract[
  list,
  Join @@ (Position[list, #] & /@ Intersection[
   list, 
   Permutations[DeleteDuplicates@Level[list, {-1}], {Length@list[[1]]}]
  ]) // Sort
]

A few examples

nonduplist@{{a, a, b}, {c, b, a}, {a, b, c}, {b, a, a}, {a, b, a}}

{{c, b, a}, {a, b, c}}

And to replicate @kglr's result

SeedRandom[1]; nonduplist@RandomInteger[5, {10, 3}]

{{0, 3, 5}, {2, 0, 3}, {1, 4, 2}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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