Deleting sub-list that contains duplicates

Question

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?

Answer 1

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}}

Answer 2

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$...

Answer 3

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}}