Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

How can sets be recursively concatenated when intersecting with each other

by joni (Initiate)
on Apr 24, 2011 at 10:21 UTC ( #901038=perlquestion: print w/replies, xml ) Need Help??

joni has asked for the wisdom of the Perl Monks concerning the following question:

Hi there. I want to recursively concatenate (union) sets that are not disjointed (the intersected set is not empty). For example, if I have the sets

(0) (0 1) (0 1 2) (1 2 3) (6 4 5)

The output should be:

((0 1 2 3) (4 5 6)
This is the code when I compare iteratively sets one by one:
use Set::Scalar; for $i ( 0 .. 4) {$cluster[$i] = Set::Scalar->new;} $cluster[0]->insert(0); $cluster[1]->insert(0,1); $cluster[2]->insert(0,1,2); $cluster[3]->insert(1,2,3); $cluster[4]->insert(5,6,4); for $i ( 0 .. 4) { for $j ( $i+1 .. 4) { if ($cluster[$i]->is_properly_intersecting($cluster[$j])) {$cluste +r[$i]=$cluster[$i]+$cluster[$j];$cluster[$j]->clear;} }}
The output is (not what I want):
(0) (0 1 2 3) (0 1 2) () (4 5 6)

Replies are listed 'Best First'.
Re: How can sets be recursively concatenated when intersecting with each other
by Corion (Pope) on Apr 24, 2011 at 11:04 UTC

    Why are you making more than one sweep across your cluster? In your first sweep, you will have collected all intersecting sets into one set already.

    You don't show how you output your data, so I can't comment on why your output is not what you want. But note that at least you found the two disjoint sets, (0 1 2 3) and (4 5 6).

Re: How can sets be recursively concatenated when intersecting with each other
by jaredor (Priest) on Apr 24, 2011 at 14:02 UTC
Re: How can sets be recursively concatenated when intersecting with each other
by jdporter (Canon) on Apr 25, 2011 at 06:44 UTC

    use Graphs.

    use Graph; use strict; use warnings; my @sets = ( [qw(0)], [qw(0 1)], [qw(0 1 2)], [qw(1 2 3)], [qw(4 5 6)], ); my $gr = new Graph undirected => 1, unionfind => 1; for my $set ( @sets ) { @$set == 1 and $gr->add_vertex( $set->[0] ); @$set <= 1 and next; $gr->add_edge( $set->[$_-1], $set->[$_] ) for 1 .. $#{$set}; } for my $set ( $gr->connected_components ) { print "( @$set )\n"; }
    I reckon we are the only monastery ever to have a dungeon stuffed with 16,000 zombies.
Re: How can sets be recursively concatenated when intersecting with each other
by SuicideJunkie (Vicar) on Apr 24, 2011 at 21:56 UTC

    FYI: you can use (0..$#cluster) rather than hardcoding magic numbers, and push onto the array to simplify your initialization (see below).

    use strict; use warnings;
    Are important to include too. Example (with array names pluralized for clarity):

    use strict; use warnings; my @sets = ( [0], [0, 1], [0, 1, 2], [1, 2, 3], [5, 6, 4], ); my @clusters; foreach my $set (@sets) { push @clusters, Set::Scalar->new->insert(@$set); } for my $i (0.. $#clusters) { ...

    Definitely put some debug prints into your loop so you can see if what it is actually doing is what you expect it to be doing at each step.

    PS:
    If this is going to expand to large sets of clusters, it would probably be a good idea to modify your algorithm such that it doesn't have to check the cleared/empty sets over and over. For large clusters, you would want an intersection test that short-circuits after the first match to return just a true/false result too.

    I'd suggest having a list of superclusters, and adding one cluster at a time. If the new cluster has no intersections with anything, add it to the list as a new supercluster. If it has an intersection with something, add it to that supercluster and keep searching. For every intersection after the first, add the intersecting supercluster to the originally matched supercluster, and then completely remove the new match (take care about the list shrinking by 1 when you do that).

    That way, your debug output could show something like:

    0 superclusters: () : adding (0)... 0 intersections. 1 supercluster: ((0)) : adding (1,2,3)... 0 intersections. 2 superclusters: ((0), (1,2,3)) : adding (0,1)... 2 intersections. 1 supercluster: ((0,1,2,3)) : adding (0,1,2)... 1 intersection.

Re: How can sets be recursively concatenated when intersecting with each other
by wind (Priest) on Apr 25, 2011 at 07:30 UTC

    jaredor already pointed out the related post from 3 weeks ago where someone wanted to do the same thing: how to find combine common elements of an array?

    However, after a little thought, I came up with a shorter solution than my original suggestion:

    use strict; use warnings; #my @array = ([11,12], [11,13], [9,8,7], [3,4], [11,4]); my @array = ([0], [0,1], [0,1,2], [1,2,3], [6,4,5]); ORIG: for my $i (0..$#array) { for my $j ($i+1..$#array) { my %seen; my @unique = grep {! $seen{$_}++} @{$array[$i]}, @{$array[$j]} +; if (@unique < @{$array[$i]} + @{$array[$j]}) { $array[$i] = \@unique; splice @array, $j, 1; redo ORIG; } } } print join(' ', @$_), "\n" for (@array);

    Note: This only works if each set contains unique elements only.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://901038]
Approved by John M. Dlugosz
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2021-03-08 10:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favorite kind of desktop background is:











    Results (124 votes). Check out past polls.

    Notices?