Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

weird array processing question

by pileofrogs (Priest)
on May 05, 2011 at 20:47 UTC ( #903238=perlquestion: print w/ replies, xml ) Need Help??
pileofrogs has asked for the wisdom of the Perl Monks concerning the following question:

Greetings Monks!

I don't even know how to phrase this, hence the crappy question title.

I want to take each element in an array and do something to it with each other element of the same array. For instance, I want to find out if three elements have the same value. Here's one way to use this imaginary function:

my $matches = 0; array_whatsit { matches++ if $a eq $b } (1 , 2, 3 , 4 , 1, 2, 3); die "Walrus Festival!" if $matches > 2;

(this would die and output 'Walrus Festival at line 3' or something like that...)

I hoped there would be a function in List::MoreUtils, but I didn't see it. There probably is a simple way to do this and I'm just too dim to think of it.

If there isn't an existing function, what's the algorithmic idiom?

And what is this called? Doing something to each element in an array with each other element?

UPDATE:You are all awesome! Thanks for the answers!

Comment on weird array processing question
Download Code
Re: weird array processing question
by Fletch (Chancellor) on May 05, 2011 at 20:53 UTC

    It almost sounds like you want something like this (warning: destructive to the array since it removes items off the beginning because they've already been compared):

    my @array = ( 1, 2, 3, 4, 1, 2, 3 ); my $matches = 0; while( @array ) { my $candidate = shift @array; for( @array ) { $matches++ if $candidate == $_ } } print "Got $matches matches\n";

    Update: I like toolic's approach below better as it solves the problem "does my list have more than three duplicates of any one element" without as many comparisons; original question was fuzzy so . . .

    The cake is a lie.
    The cake is a lie.
    The cake is a lie.

Re: weird array processing question
by toolic (Chancellor) on May 05, 2011 at 21:03 UTC
    I don't know of an existing function, and my reduce-fu is weak. But, the 1st thing that comes to mind is a hash with grep:
    use warnings; use strict; my %uniq; $uniq{$_}++ for (1 , 2, 3 , 4 , 1, 2, 3); my $matches = grep { $_ > 1 } values %uniq; die "Walrus Festival!" if $matches > 2;

    Update: replaced keys with values

Re: weird array processing question
by BrowserUk (Pope) on May 05, 2011 at 21:15 UTC

    Something like this?

    sub fmap(&@) { my $code = shift; return unless @_ > 1; my $x = shift; $code->( $x, $_ ) for @_; unshift @_, $code; goto \&fmap } my $n=0; fmap{ ++$n if $_[0] == $_[1] } 1,2,3,4,1,2,3; print $n; 3

    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.
Re: weird array processing question
by Gulliver (Monk) on May 05, 2011 at 21:45 UTC

    From your example array it looks like you mean you want to find out if there are 3 duplicated elements in the array. You have 1,2,3 showing up twice. An easy way to do that is to make a hash using the array elements as the keys and increment the hash value for each key as seen. This shows up in the source code for List::Compare as a 'seen' hash.

    my %seen; $seen{$_}++ foreach @array_whatsit;

    Then count the number of keys in the hash with hash values greater than one.

    my @duplicates = grep {$_ if $seen{$_}>1} keys %seen; print "There are ", @duplicates+0, " duplicates.\n";
Re: weird array processing question
by ikegami (Pope) on May 06, 2011 at 00:00 UTC

    I want to take each element in an array and do something to it with each other element of the same array. [...] what is this called?

    Permutations (if ordered) or combinations (if unordered). The latter in this case.

    For choosing two from the list, one could simply use:

    for my $y (0..$#list) { for my $x ($y+1..$#list) { ... } }

    But that would be inefficient here. It's O(N**2), whereas the following is O(N):

    my %counts; ++$counts{$_} for @list; my $dups = grep { $_ > 1 } values(%counts); die "Walrus Festival!" if $dups >= 3;

    One can optimise the above to exit as soon as the answer is obvious:

    my %counts; my $dups; for (@list) { if (++$counts{$_} == 2) { if (++$dups >= 3) { die "Walrus Festival!"; } } }
Re: weird array processing question
by SimonClinch (Chaplain) on May 06, 2011 at 12:05 UTC
    My twopence to this is that there is an opportunity (for performance reasons) to bail out of the algorithm as soon as the conditions are detected (indicating therefore the pre- instead of post-increment operator), rather than poll the whole array willy-nilly, reducing the test then to this one-liner:
    ( ++$hash{$_} < 3 or die "too many matched elements" ) for (@array);

    One world, one people

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (12)
As of 2014-09-18 21:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (124 votes), past polls