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
On Sun, 11 Sep 2011, tim vets wrote:
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