# Deleting sub-list that contains duplicates

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?

• Select[listOfThreeItemLists, Signature[#] != 0 &]? Commented Oct 16, 2018 at 18:58
• Select[listOfThreeItemLists, DuplicateFreeQ]? Commented Oct 16, 2018 at 19:01

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

• 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. Commented Oct 18, 2018 at 19:33
• @KevinAusman, my pleasure. Thank you for the accept.
– kglr
Commented Oct 18, 2018 at 19:34

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

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

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