Re^5: algorithm for 'best subsets'

[halley]

Pseudocode for my version of the algorithm (without using G::UF or any graph concept at all), if I understand it correctly. By "kbits" I mean a keyword bit vector. By "parts" I mean partitions. Am I missing something?

  # bag of parts

  # for each item
    # for each existing part
      # if this item's kbits intersect this part's kbits,
        # union up the keywords
        # for all other parts
          # if this part's kbits intersect that part's kbits,
            # merge that part into this part
    # prune parts emptied by merger
    # create a new part if no intersections found

It seems to work, and scans my whole current database of 5810 keywords in 6628 items in about three seconds.

Unfortunately, it grows to about 5 partitions maximum, and by the time it's done, it has merged back everything into one partition. I think that's the fault of my keywords pruning, though. Even though I filter out the 100 most boring prepositions and articles, I need to find out the remaining words that cause the most mergers...

Update: How depressing. Not only is 'war' the most common keyword in modern history, but it appears to be the common thread amongst all of the events as well; removing that one keyword broke the historical context into five separate partitions.

[tall_man]

Ok, halley, it looks like you're right. Since we can "or" the bit sets, UnionFind is redundant in this case. UnionFind is meant for the case when one must build up the partitions from a list of edges alone. Since we don't know the edges and we have an easy set partition membership test, your algorithm is preferable.

I'm glad this was useful to break down your problem, even if it turned up a depressing word.