Re: Equivalence classes from equivalence relation and fingerprints

UPDATE: I like tye's solution better than mine.

I think you're most of the way there. I haven't written the code, but the procedure would go like this:

Get a list of your objects, sorted by fingerprint (not just a list of indexes).

Loop over the list with something like:

my $run_start = 0;
foreach my $index ( 0 .. @sorted - 2 ) {
    if ( ! prop_matching( $sorted[$index],
                          $sorted[$index+1] ) ) {
        output_sets( $run_start, $index );
        $run_start = $index + 1;
    }
}
[download]

The sub output_sets starts with return if ( $run_start == $index );
It then loops through the items in the run, using prop_matching to group them. Just take the first one, loop through and print everything that matches, remove those from the list, and repeat. You want to avoid printing the ones that match nothing.

Comment on Re: Equivalence classes from equivalence relation and fingerprints Select or Download Code

Replies are listed 'Best First'.
Re^2: Equivalence classes from equivalence relation and fingerprints by ambrus (Abbot) on Jan 19, 2007 at 14:15 UTC
This solves only one of my two problems: the runs of matching properties longer than two objects. The other problem is when two objects of matching property are not adjacent even after the sorting because they are separated by an object with different property but accidentally matching fingerprint.	[reply]
Re^3: Equivalence classes from equivalence relation and fingerprints by kyle (Abbot) on Jan 19, 2007 at 16:52 UTC
The other problem is when two objects of matching property are not adjacent even after the sorting because they are separated by an object with different property but accidentally matching fingerprint. I think it does that too, actually. It's not as efficient as tye's solution, but it should work. I probably didn't describe it well enough, though, so let me have another crack at it. The (unwritten) `output_sets` function accepts a range that specifies a group of objects that have matching fingerprints. Turn that range into a list (say `@fpmatches`). `shift` the first item off `@fpmatches` and compare it to every other item in `@fpmatches` (with `prop_matching`). This should find every object with matching properties, regardless of how they sorted. The ones that match, output as a set, and remove from the `@fpmatches` list. Go back and `shift` off another object to compare, until the list is empty.	[reply] [d/l] [select]