# [PD] filtering out non-unique, unordered lists from collection of lists

Mathieu Bouchard matju at artengine.ca
Sun Sep 11 18:10:17 CEST 2011

```On Sun, 11 Sep 2011, tim vets wrote:

> What's a good way to compare a list to a collection of other lists to
> see whether it's already present in the collection? From a collection of
> lists, I want to keep only one instance of each unique list. Also, I
> would have to treat the lists as 'unordered' so that "1 2 2 3 4" is
> considered as being the same as "2 4 3 2 1", and only one of them will
> be kept. thanks, Tim

Sort them. This will treat them as unordered, because it will destroy
their previous order, to replace them with a predictable order.

This will work as long as the comparison function does not find that two
different values are equal. This can happen if you sort 2-D points by
distance from origin, or if you sort (pitch,volume) pairs by pitch, for
example, but it will not happen if you sort individual floats the ordinary
way.

If your number of possible values is quite small, e.g. if it's limited to
integers from 0 to 6, then you can make a reversible histogram, where each
list position represents the number of occurrences of a certain number in
the original list. Thus :

list 0 1 5 3 1 6 3 1 3 5 6 2 4 4

has histogram :

list 1 3 1 3 2 2 2

(0 occurs 1 time, 1 occurs 3 times, 2 occurs 1 time, 3 occurs 3 times...)

and because it's reversible, you can easily recover the sorted list from
it :

list 0 1 1 1 2 3 3 3 4 4 5 5 6 6

which shows that it's possible to sort numbers in O(n) steps, as long as
there are very few possible values (of the sort criterion). This is a rare
exception to the law of minimum sort time O(n log n) and it's because
we're not relying on comparisons.

_______________________________________________________________________
| Mathieu Bouchard ---- tél: +1.514.383.3801 ---- Villeray, Montréal, QC
```