### Re: Finding largest common subset in lists?

by broquaint (Abbot)
 on Jun 05, 2003 at 09:45 UTC ( #263260=note: print w/replies, xml ) Need Help??

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

Not exactly vastly mystical but this should do the trick (although it hasn't been thoroughly tested)

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
You might also find some roughly applicable questions under Longest Common Substring.
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
With use warnings it gives a Use of uninitialized value in string eq at... warning. Small off-by-one error.

Replacing

push @tmp, \$a[\$_] if ( \$a[\$_ + 1]) eq ( \$b[\$map{\$a[\$_]} + 1] ) or @tmp >= 1;
with
push @tmp, \$a[\$_] if (\$a[\$_ + 1] and \$b[\$map{\$a[\$_]} + 1] and ( \$a[\$_ + 1]) eq ( \$b[\$map{\$a[\$_]} + 1] ) or @tmp >= 1);
makes Perl happy again.

Arjen

Re: Re: Finding largest common subset in lists?
by zby (Vicar) on Jun 05, 2003 at 10:58 UTC
I just felt it was too simple. For @a = qw(a b c); @b = qw(a b x c) it prints LCS - a b c .
Re: Re: Finding largest common subset in lists?
by zby (Vicar) on Jun 05, 2003 at 12:44 UTC
The updated code does not work for  @a = qw(a b c d); @b = qw(a b x b c d). It prints a b c d. The output is suprising for me - I created the inputs to catch another kind of mistake. I believe you can't do it in one sweep.
The output is due to the fact that 'b' is repeated in @b so the offset in %map is for the second 'b'. I think I'll leave the code as it is for the time being and just add a caveat that it won't work when there are duplicates in @b. Thanks once again :)

_________
broquaint

It was aimed at duplicates, but I did not take into account the details - just the general algorithm. I believe you can not do it in one sweep when there are duplicates.

Create A New User
Node Status?
node history
Node Type: note [id://263260]
help
Chatterbox?
 [erix]: Alvin Lee (Ten Years After) played a jazzguitar ("Big Red"), a good warm sound [stonecolddevin]: I think Stevie Ray is one of maybe 2 or 3 people that could take a Hendrix song and make you go "...huh. this is close." https://open. spotify.com/track/ 0UVM9trirBK5s1xBwL oVhZ [Corion]: Sadly I must go to bed now :-| See y'all! [erix]: I really loved/love this "Recorded Live" record, 1973 (yes, I'm that old) [stonecolddevin]: goodnight Corion [erix]: cya Corion :) [stevieb]: Joan Jett, Hendrix, Neil Young, Dave Keuning (The Killers)... I have my mind elsewhere so I'm limited in my capacity to think about this righ tnow ;) [stonecolddevin]: I will say John Mayer is an excellent guitarist, I don't like his music but he's pretty damn good

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (5)
As of 2017-06-22 21:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (531 votes). Check out past polls.