Here's an algorithm that performs the operation, in a slightly more Perl-ish manner (heavy use of shift), but destroys the copies of the lists. It could easily be modified not to do so, by using a list of array offsets, but this should give you a start. In any case, it's just a heck of a lot easier in Perl to shift and always check the first element than to try to keep track of a list of array offsets.

I don't know if it's optimal, but I'm happy with it:

use Data::Dumper;

my @sets =
    ([ 0, 1, 2, 3,          7, 8, 9, 10, 11, 12, 13, 14, 15,     ],
     [ 0,       3,          7, 8,    10, 11,     13, 14,     16, ],
     [ 0, 1, 2, 3,    5,    7, 8,    10, 11, 12, 13, 14,     16, ],
     [       2, 3, 4,    6, 7, 8,    10, 11, 12,     14,     16, ],
     [ 0, 1, 2, 3,          7, 8, 9, 10, 11,     13, 14, 15,     ]);

my @common = ();

### helpers
sub max_element {
    my $max = -1;
    for (@sets) {
        $max = $_->[0] if $_->[0] > $max;
    }
    return $max;
}

sub all_the_same {
    my $element;
    for (@sets) {
        if (not defined $element) {
            $element = $_->[0];
        } else {
            return 0 if $element != $_->[0];
        }
    }
    return 1;
}

### main loop
my $done = 0;
while (not $done) {

    foreach (@sets) {
        $done++ if @$_ == 0;
    }

    if (all_the_same()) {
        push @common, $sets[0][0];
        shift @$_ for @sets;
    } else {
        my $max = max_element();
        for (@sets) {
            shift @$_ if $_->[0] < $max;
        }
    }


    ## uncomment these to see how it works step by step:
    # print Dumper(\@sets, \@common), "\n";
    # <STDIN>

}

print "@common\n";
[download]

Here's a pseudocode breakdown of the algorithm, for illustrative purposes.

common_elements ::= empty list;

while all lists are non-empty; do
  if the first elements of all the lists are the same
    add that element to common_elements
  else
    max_element ::= maximum first element of all lists
    foreach list; do
      if first element of list < max_element;
        shift it off the list
  endif
done
[download]

Works kinda like a merge-sort by moving down all the lists in parallel. I don't know if that's what yours is trying to do. I can't quite grok it at the moment. Update: After adding some Dumper statements to your code, it seems like yours is doing a very similar algorithm, as you said, in a very C++ way. I'm not so sure what to think about the last MAIN; statement you have there. ;-)

There is at least one part where code could be improved: the max_element sub could also return information about which arrays had non-maximum elements, so those arrays could easily be shifted. To do this cleanly and efficiently requires more cleverness than I have, however.

HTH,

blokhead

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.