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

[Mathieu Bouchard]

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