in reply to Finding largest common subset in lists?
Update: fixed code to work with zby's case and hopefully any other case.
Update: code won't work with duplicates in the second list
HTH
Update: code won't work with duplicates in the second list
Not exactly vastly mystical but this should do the trick (although it hasn't been thoroughly tested)
You might also find some roughly applicable questions under Longest Common Substring.use strict; my @a = qw/ fred bob joe jim mary elaine /; my @b = qw/ frank joe jim mary bob /; print "LCS[anjiro] - ", join($", get_lcs(\@a, \@b)), $/; @a = qw/ a b c /; @b = qw/ a b x c /; print "LCS[zby] - ", join($", get_lcs(\@a, \@b)), $/; sub get_lcs { my @a = @{ +shift }; my @b = @{ +shift }; my %map = map { $b[$_] => $_ } 0 .. $#b; my(@lcs, @tmp); for(0 .. $#a) { next unless exists $map{$a[$_]} or $a[$_ + 1] eq $b[$map{$a[$_]} + 1]; push @tmp, $a[$_] if $a[$_] eq $b[$map{$a[$_]}]; if($a[$_ + 1] ne $b[$map{$a[$_]} + 1]) { @lcs = @tmp if @tmp > @lcs; @tmp = (); } } @lcs = @tmp if @tmp > @lcs; return @lcs; } __output__ LCS[anjiro] - joe jim mary LCS[zby] - a b
HTH
_________
broquaint
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Re: Finding largest common subset in lists?
by Aragorn (Curate) on Jun 05, 2003 at 10:21 UTC | |
Re: Re: Finding largest common subset in lists?
by zby (Vicar) on Jun 05, 2003 at 10:58 UTC | |
Re: Re: Finding largest common subset in lists?
by zby (Vicar) on Jun 05, 2003 at 12:44 UTC | |
by broquaint (Abbot) on Jun 05, 2003 at 12:58 UTC | |
by zby (Vicar) on Jun 05, 2003 at 13:20 UTC |
In Section
Seekers of Perl Wisdom