Array subtraction, like sets

[Robin Sheat]

Hey there, what is a nice way of doing what this looks like it should
do:

@a=([1,2,3],[5,5,5],[9,8,7]);
@b=([5,5,5],[1,2,3]);
@c=@a-@b;

and have @c == ([1,2,3]);

Is there a good way of doing this? (I've tried the obvious things on the
command line, to no avail). I could probably write a function for it
without too much trouble, but it could get ugly :)

cheers,
--
Robin <robin@kallisti.net.nz> JabberID: <eythian@jabber.org>

Hostes alienigeni me abduxerunt. Qui annus est?

PGP Key 0x776DB663 Fingerprint=DD10 5C62 1E29 A385 9866 0853 CD38 E07A 776D B663

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAGeYyzTjgendttmMRAlSoAKCMmy6fv/W82+h/ORChpit/GKZK8ACfSlkJ
TvYssruqfKStKALHfWBAXXc=
=VV9W
-----END PGP SIGNATURE-----

[Wiggins D Anconia]

>

> Hey there, what is a nice way of doing what this looks like it should
> do:
>

Going to need more info about what you think this looks like it should
do, because I (and maybe others here) lack the math skills to get your
answer, funny, I got [9,8,7].

> @a=([1,2,3],[5,5,5],[9,8,7]);
> @b=([5,5,5],[1,2,3]);
> @c=@a-@b;
>
> and have @c == ([1,2,3]);
>
> Is there a good way of doing this? (I've tried the obvious things on the
> command line, to no avail). I could probably write a function for it
> without too much trouble, but it could get ugly :)
>

The obvious things are inside your head, my obvious thing would be to go
immediately to CPAN and look for the formal name of whatever it is you
are attempting, one (mediocre at best) guess would be to start at either:

[url]http://search.cpan.org/~ulpfr/Math-Matrix-0.4/Matrix.pm[/url]

Or,

[url]http://search.cpan.org/modlist/Data_and_Data_Types/Math[/url]

[url]http://danconia.org[/url]

[Robin Sheat]

On Fri, Jan 30, 2004 at 07:48:35AM -0700, Wiggins d Anconia wrote:

> Going to need more info about what you think this looks like it should
> do, because I (and maybe others here) lack the math skills to get your
> answer, funny, I got [9,8,7].

Thats what I get for not profraedinng, the result should be:
@c = [9,8,7]

> > @a=([1,2,3],[5,5,5],[9,8,7]);
> > @b=([5,5,5],[1,2,3]);
> > @c=@a-@b;

> The obvious things are inside your head, my obvious thing would be to go
> immediately to CPAN and look for the formal name of whatever it is you
> are attempting, one (mediocre at best) guess would be to start at either:

Well, I ended up having to write a function, it wasn't quite as ugly as
I thought (pasted below, for the benefit of others). However, if there
was a better way, I'd like to know how :)

Heres what I got (odd seeming indents courtisy of emacs):

#####
# subArray - takes two array references, and subtracts any instances
# of the arrays in the second one from the first one. Returns the new list.
sub subArray {
my @a = @{ shift() };
my @b = @{ shift() };
my @c;
OUTER: foreach my $outer (@a) {
INNER: foreach my $inner (@b) {
next OUTER if ($outer == $inner);
}
push @c, $outer;
}
return @c;
}


--
Robin <robin@kallisti.net.nz> JabberID: <eythian@jabber.org>

Hostes alienigeni me abduxerunt. Qui annus est?

PGP Key 0x776DB663 Fingerprint=DD10 5C62 1E29 A385 9866 0853 CD38 E07A 776D B663

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAGnRkzTjgendttmMRApZBAKCxRFa78IlAqZ82L6kySK 0MsY++WACfc4n+
9chanrs3DIeguMx7ZKei66A=
=eo/a
-----END PGP SIGNATURE-----

[Jeff 'Japhy' Pinyan]

On Jan 31, Robin Sheat said:

>> > @a=([1,2,3],[5,5,5],[9,8,7]);
>> > @b=([5,5,5],[1,2,3]);
>> > @c=@a-@b;

>#####
># subArray - takes two array references, and subtracts any instances
># of the arrays in the second one from the first one. Returns the new list.
>sub subArray {
> my @a = @{ shift() };
> my @b = @{ shift() };
> my @c;
> OUTER: foreach my $outer (@a) {
> INNER: foreach my $inner (@b) {
> next OUTER if ($outer == $inner);
> }
> push @c, $outer;
> }
> return @c;
>}

Well, that only works if $a[0] is [1,2,3] and $b[1] is $a[0] -- that is,
the EXACT SAME reference. It won't work if $b[1] is its own [1,2,3].

The simplest way to do this type of thing is to use a hash.

sub array_diff {
my ($first, $second) = @_;
my %diff = map { "@$_" => 1 } @$second;
return [ map !$diff{"@$_"}, @$first ];
}

This builds a hash of the elements to subtract, and then it goes through
the elements of the set being subtracted FROM, and returns only those
elements NOT in the subtract-me hash.

It might look convoluted, but it's efficient. It also prevents you from
doing the icky

for this (set a) {
for that (set b) {
compare this and that
}
}

--
Jeff "japhy" Pinyan [email]japhy@pobox.com[/email] [url]http://www.pobox.com/~japhy/[/url]
RPI Acacia brother #734 [url]http://www.perlmonks.org/[/url] [url]http://www.cpan.org/[/url]
<stu> what does y/// stand for? <tenderpuss> why, yansliterate of course.
[ I'm looking for programming work. If you like my work, let me know. ]

[Bob Showalter]

Robin Sheat wrote:

> Hey there, what is a nice way of doing what this looks like it should
> do:
>
> @a=([1,2,3],[5,5,5],[9,8,7]);
> @b=([5,5,5],[1,2,3]);
> @c=@a-@b;
>
> and have @c == ([1,2,3]);
>
> Is there a good way of doing this? (I've tried the obvious things on
> the command line, to no avail). I could probably write a function for
> it without too much trouble, but it could get ugly :)

See perldoc -q 'How do I compute the difference of two arrays?'

There are also numerous Set manipulation modules on CPAN. Try:

[url]http://search.cpan.org/search?query=set%3A%3A&mode=module[/url]

[Robin Sheat]

On Fri, Jan 30, 2004 at 10:33:27AM -0500, Jeff 'japhy' Pinyan wrote:

> Well, that only works if $a[0] is [1,2,3] and $b[1] is $a[0] -- that is,
> the EXACT SAME reference. It won't work if $b[1] is its own [1,2,3].

Hmm, right. Not so good. I had thought of that, and thought I tested it
in that situation, but I can't reproduce those tests now, so obviously
I messed something up. Your method looks somewhat nicer than mine,
anyway, so I may steal that :)

cheers,
--
Robin <robin@kallisti.net.nz> JabberID: <eythian@jabber.org>

Hostes alienigeni me abduxerunt. Qui annus est?

PGP Key 0x776DB663 Fingerprint=DD10 5C62 1E29 A385 9866 0853 CD38 E07A 776D B663

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAGwsZzTjgendttmMRAtV7AJ90d60DwE3y63iMKLilM3 BiyWH0YgCeLtKQ
uDAwJx2Qs/rh6Zesz1Nmfq8=
=8ZZF
-----END PGP SIGNATURE-----

[Robin Sheat]

On Fri, Jan 30, 2004 at 10:33:27AM -0500, Jeff 'japhy' Pinyan wrote:

> sub array_diff {
> my ($first, $second) = @_;
> my %diff = map { "@$_" => 1 } @$second;
> return [ map !$diff{"@$_"}, @$first ];
> }

amended to:
return [ grep !$diff{"@$_"}, @$first ];
(for the benefit of anyone else looking at this), and it works a charm
(with the really minor exception of being an array too deep, but that is
easy fixed.)
cheers,
--
Robin <robin@kallisti.net.nz> JabberID: <eythian@jabber.org>

Hostes alienigeni me abduxerunt. Qui annus est?

PGP Key 0x776DB663 Fingerprint=DD10 5C62 1E29 A385 9866 0853 CD38 E07A 776D B663

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAHHztzTjgendttmMRAgCFAJ47GyxvJRNmXLPFtJLNJb rex6D0bgCdENvn
rQqVX5uehAixuMqr7QrZfRY=
=p+7N
-----END PGP SIGNATURE-----

[Jeff 'Japhy' Pinyan]

On Feb 1, Robin Sheat said:

>On Fri, Jan 30, 2004 at 10:33:27AM -0500, Jeff 'japhy' Pinyan wrote:

>> sub array_diff {
>> my ($first, $second) = @_;
>> my %diff = map { "@$_" => 1 } @$second;
>> return [ map !$diff{"@$_"}, @$first ];
>> }

>amended to:
> return [ grep !$diff{"@$_"}, @$first ];
>(for the benefit of anyone else looking at this), and it works a charm
>(with the really minor exception of being an array too deep, but that is
>easy fixed.)

Thanks for that fix. I wrote 'map' once, I wrote it twice. Silly
mistake.

As far as it being an array too deep, I did that because it takes two
array refs of array refs as arguments, so I made it return an array ref of
array refs.

--
Jeff "japhy" Pinyan [email]japhy@pobox.com[/email] [url]http://www.pobox.com/~japhy/[/url]
RPI Acacia brother #734 [url]http://www.perlmonks.org/[/url] [url]http://www.cpan.org/[/url]
<stu> what does y/// stand for? <tenderpuss> why, yansliterate of course.
[ I'm looking for programming work. If you like my work, let me know. ]