Re^2: how to find combine common elements of an array?

With the recent question, How can sets be recursively concatenated when intersecting with each other, I ended up revisiting these solutions and providing a streamlined answer. I must say that I'm definitely a fan of jaredor's solution below, but I noticed a couple areas where yours could be improved efficiency wise and one potential bug:

Efficiency: loop $j from $i+1 to $#array instead of the entire array.
Efficiency: using redo instead of goto so that fully reduced elements don't need to be gone over again.
bug: dedup will potentially drop numbers that are substrings of other numbers. ie 11 and 111.

Here's my suggested changes applied to your solution:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

my @array = ("11 12","11 13", "9 8 7", "3 4", "11 4 111") ;

## combine
AGAIN: for my $i ( 0 .. $#array ) {
    for my $j ( $i+1 .. $#array ) {
        for my $n (split ' ', $array[ $j ]){
            if( $array[ $i ] =~ m[\b$n\b] ) {
                $array[ $i ] .= ' ' . splice @array, $j, 1;
                redo AGAIN;
            }
        }
    }
}
## dedup
for ( @array ) {
    1 while s[(\b\d+)\s(?=.*\b\1\b)][]g;
}

pp \@array;
[download]

Comment on Re^2: how to find combine common elements of an array? Download Code

Replies are listed 'Best First'.
Re^3: how to find combine common elements of an array? by BrowserUk (Patriarch) on Apr 25, 2011 at 16:40 UTC
I noticed a couple areas where yours could be improved efficiency wise and one potential bug: That is a big improvement, especially fixing the bug. The redo instead of goto is so obvious ... yet I didn't see it. I'm definitely a fan of jaredor's solution below Me too. At least, jaredor's second solution. Which I'd missed till now. I did see his original solution and my eyes zeroed in on this line: `my @sg = sort {$a<=>$b} uniq grep {defined} (@v2g{@$i}, min @$i);` [download] There's a lot of potentially expensive processing going on in that one line. Repeating that every time around the outer loop of a large set of data smacked of "expensive". By contrast, his second solution is almost magical in its simplicity and deserves elevating to tutorial. I wouldn't mind betting that many of the graphing packages (and their authors) could learn a lot from that unremarkable looking piece of code. then realized that there didn't need to be an identified element per subgraph... Don't you just love understatement :) Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^4: how to find combine common elements of an array? by wind (Priest) on Apr 26, 2011 at 02:23 UTC
Don't you just love understatement :) Aye, I'm very much in awe of his use of references in the solution. Would just never think to use uniq in that way. I actually noticed another potential problem with your and my later solution. `for my $i (0..$#array)` doesn't recalculate the max value with each iteration. It isn't a problem given it does for the inner loop, but it could potentially lead to issues in a different algorithm, so glad I noticed this.	[reply] [d/l]