efficient different sized list comparisons
Question: I wish to compare around 1000 lists of varying size. Each list might have
thousands of items. I want to compare each pair of lists, so potentially
around 500000 comparisons. Each comparison consists of counting how many of
the smaller list exists in the larger list (if same size, pick either
list).Ultimately I want to cluster the lists using these counts. I want to be
able to do this for two types of data:

  1. any textual data
  2. strings of binary digits of the same length.

Is there an efficient way of doing this in python? I've looked at LShash and
other clustering related algorithms, but they seem to require same length
lists. TIA.

An example to try to clarify what I am aiming to do:

List A: car, dig, dog, the.

List B: fish, the, dog.

(No repeats in any list. Not sorted although I suppose they could be fairly
easily. Size of lists varies.)

Result:2, since 'dog' and 'the' are in both lists.

In reality the length of each list can be thousands and there are around 1000
such lists, each having to be compared with every other.

Continuing the example:

List C: dog, the, a, fish, fry.

Results: AB: 2 AC: 2 BC: 3


Answer: Nothing is going to be superfast, and there's a lot of data there (half a
million results, to start with), but the following should fit in your time and
space budget on modern hardware.

If possible, start by sorting the lists by length, from longest to shortest.
(I don't mean sort each lists; the order of elements in the list is
irrelevant. I mean, sort the collection of lists so that you can process the
longest list first.) The only point of doing this is to allow the similarity
metrics to be stored in a half-diagonal matrix instead of full matrix, which
saves half the matrix space. So if you don't know the length of the lists
before you start, it's not a crisis; it just means that you'll need a bit more
space.

**Note 1:** The important thing is that the metric you propose is completely
symmetric as long as no list has repeated elements.Without repeated elements,
the metric is simply `|A⋂B|`, regardless of whether `A` or `B` is longer, so
when you compute the size of the intersection of `A` and `B` you could fill in
the similarity matrix for both `(A,B)` and `(B,A)`.)

**Note 2:** The description of the algorithm seemed confusing to me when I
reread it so I changed the word "list" to "_list_ " when it refers to one of
the thousand input _lists_ , leaving "list" to mean an ordinary Python list.
Because lists can't be keys in Python dictionaries, working on the assumption
that _lists_ are implemented as lists, it's necessary to somehow identify each
_list_ with an identifier which can be used as a key. I hope that's clear.

### The Algorithm:

We need two auxiliary structures: one is the (half-diagonal) result matrix,
keyed by pairs of _list_ identifiers, which we initialize to all 0s. The other
one is a dictionary keyed by unique data element, mapping onto a list of
_list_ identifiers.

Then, taking each list in turn, for each element in that list we do the
following:

  1. If the element is not yet present in the dictionary, add it, mapping to a single element list consisting of the current _list's_ identifier.

  2. If the element is present in the dictionary but the last element in the corresponding list of ids is the current id, then we've found a repeated element. Since we don't expect repeated elements, either ignore it or issue an error message.

  3. Otherwise, we've seen the element before and we have a list of identifiers of _lists_ in which the element appears. For each such identifier, increment the similarity count between the current identifier and the identifier in the list. (Note that if we scan _lists_ in reverse order by length, all the identifiers in the list correspond to _lists_ which are at least as long as the current _list_ , which is why we sorted the _lists_ in the first place.) Finally, append the current identifier to the end of the list, so that the next time that data element is found, the current _list_ will be present.

That's it. The space requirement is `O(N2 + M)` where `N` is the number of
_lists_ and `M` is the total size of all the lists. The time requirement is
essentially `O(M2)` in the worst case -- that being the case where every
_list_ has exactly one element and they are all the same element. (More
precisely, it's the sum of the squares of the frequencies of each unique
element.)

