### Re^2: Finding Combinations of Pairs

by tilly (Archbishop)
 on Jan 14, 2009 at 05:15 UTC ( #736139=note: print w/replies, xml ) Need Help??

in reply to Re: Finding Combinations of Pairs
in thread Finding Combinations of Pairs

```#! /usr/bin/perl -w
use strict;

my %pair_count;
for (<>) {
\$pair_count{\$_}++ for get_pairs(grep length \$_, split /\s/, \$_);
}

my \$comp = sub (\$\$) {-(\$pair_count{\$_[0]} <=> \$pair_count{\$_[1]})};
print((sort \$comp keys %pair_count)[0], \$/);

sub get_range_iterator {
my (\$start, \$end) = @_;
return sub {
if (\$start <= \$end) {
return \$start++;
}
else {
return;
}
}
}

sub get_pairs {
my \$outer_iter = get_range_iterator(0, \$#_);
my \$i = \$outer_iter->();
while (defined(\$i)) {
my \$inner_iter = get_range_iterator(\$i+1, \$#_);
my \$j = \$inner_iter->();
while (defined \$j) {
push @answer, join " ", sort @_[\$i, \$j];
\$j = \$inner_iter->();
}
\$i = \$outer_iter->();
}
}

Replies are listed 'Best First'.
Re^3: Finding Combinations of Pairs
by grinder (Bishop) on Jan 14, 2009 at 08:38 UTC

Or else you offer an answer that appears to be well laid out and straight-forward, but scales abysmally...

• another intruder with the mooring in the heart of the Perl

Re^3: Finding Combinations of Pairs
by Limbic~Region (Chancellor) on Jan 14, 2009 at 15:03 UTC
tilly,

It doesn't look too much like homework to me but another idea would be to use code obviously beyond that of the course?

Cheers - L~R

Re^3: Finding Combinations of Pairs
by andye (Curate) on Jan 14, 2009 at 17:21 UTC
I like this solution, because it's so simple and efficient:

```#!/usr/bin/perl -w
use strict;

my @lines = <DATA>;

my (%words, %count);
@words{map {split ' '} @lines} =1;
my @uniq = keys %words;                 # create list of unique words

foreach my \$i (0 .. \$#uniq - 1) {
foreach my \$j (\$i+1 .. \$#uniq) {

# count the pairs
do { \$count{"\$uniq[\$i] \$uniq[\$j]"}++ if /\$uniq[\$i]/ an
+d /\$uniq[\$j]/ } foreach @lines;

}
}

print   map "\$_ : \$count{\$_}\n",                # print the pairs in s
+orted order
sort {\$count{\$a} <=> \$count{\$b}}
keys %count;

__DATA__
dog monkey cat
cat ball stone
monkey iron cat zoo

(NB see parent node)

andye,
like this solution, because it's so simple and efficient:

It has at least one bug and I am not sure why you think it is efficient.

First the bug. You have /\$uniq[\$i]/. This can do the wrong thing for at least two reasons. The first is that it will match "and" in the line of "where is the sand" even though the word "and" never appears. The second reason is that you haven't use \Q\E or quotemeta to ensure any metacharacters are escaped. It doesn't take case into consideration either, but I am not sure any of the solutions do (including my own).

Another potential bug is the fact that you don't consider that in the line "hello world goodbye cruel world" that each pairing of world should double and not be counted once. I am not sure if this is or isn't a requirement but it is a bug in one intepretation.

As to why it isn't efficient. This can be done in a single pass and yet your solution has you going through every line in the data (N^2 - N) / 2 times (where N = # of unique words). In other words, you check every single pairing of unique word against every single line even if the word doesn't appear on that line.

Cheers - L~R

In the context of a discussion about providing obfuscated and inefficient answers that look reasonable, I assumed that that post was a well-executed joke.

Create A New User
Node Status?
node history
Node Type: note [id://736139]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2020-10-26 02:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite web site is:

Results (249 votes). Check out past polls.

Notices?