artist has asked for the wisdom of the Perl Monks concerning the following question:

Hi, May be this is very simple.
How to find out how many items at max, in the array are in order.
Example: 
Ordered Array: (1,2,3,8,4,5,6)
Given Array:(2,1,4,3,5)
(2,3,5)
(1,3,5)  
(2,4,5)  
(1,4,5)

In the above case given array as max 3 elements which are ordered. This is part of puzzle, which I am trying to solve. Any practical usage would be insightfull!.

Thanks,
Artist

Replies are listed 'Best First'.
Re: Items in Order
by djantzen (Priest) on Dec 11, 2002 at 21:37 UTC

    I think this does what you mean, assuming you want to find the longest subset of increasing integers: 

    my @a = (1,2,4,8,4,5,6,7,8); # sample data
my ($current, $previous);
my $tmp_max = 1;
my $max = 1;

while (@a) {
  $previous = shift(@a) ;
  $current = $a[0] or last;
  if ($previous + 1 == $current) { # or $previous < $current if number
+s may increase by more than 1
    $tmp_max++;
  } else {
    $tmp_max = 1;
  }
  $max = $tmp_max if ($tmp_max > $max);

}
print "$max\n";

    [download]

    Given the sample data, prints "5", for 4-8.

    Update: alas, I seem to have answered the wrong question {chagrin}.

[reply]
[d/l]
(tye)Re: Items in Order
by tye (Sage) on Dec 11, 2002 at 22:23 UTC

    I couldn't decipher what you are using "Ordered Array: (1,2,3,8,4,5,6)" for. But, finding all subsets from (2,1,4,3,5) of length 3 where the members appear in order, you can use: 

    sub genOrderedSubList {
    my $size= shift @_;
    my @list= @_;
    my @idx= ( -1 );
    return sub {
        my $i= $#idx;
        while(  1  ) {
            do {
                ++$idx[$i];
                if(  $#list < $idx[$i]  ) {
                    if(  --$i < 0  ) {
                        @idx= ( -1 );
                        return;
                    }
                    redo;
                }
            } while(  0 < $i
                &&  $list[$idx[$i]] <= $list[$idx[$i-1]]  );
            return  @list[@idx]   if  $i == $size-1;
            $idx[$i+1]= $idx[$i];
            ++$i;
        }
    }
}

@ARGV= ( 3, 2,1,4,3,5 )   if  ! @ARGV;
my $gen= genOrderedSubList( @ARGV );
my @res;
while(  @res= $gen->()  ) {
    print "@res\n";
}

    [download]

            - tye
[reply]
[d/l]
Re: Items in Order
by pg (Canon) on Dec 12, 2002 at 03:45 UTC
    A very short and neat recursive solution: 
    use Data::Dumper;

use strict;
use warnings;

sub move {
   my ($parn, $chld, $result, $index, $ordr, $chain, $len) = @_;
   if ($index > $#{$chld}) {
      $result->{$chain} = $len;
      return;
   } else {
      move($parn, $chld, $result, $index + 1, $parn->{$chld->[$index]}
+, "$chain,$chld->[$index]", $len + 1) if ($parn->{$chld->[$index]} > 
+$ordr);
      move($parn, $chld, $result, $index + 1, $ordr, $chain, $len);
   }
}

my $a = [1,2,3,8,4,5,6];
my $index = 0;
my %a = map {$_=>$index ++} @{$a};
my $b = [2,1,4,3,5];
my $result = {};

move(\%a, $b, $result, 0, -1, "", 0);
print Dumper($result);

    [download]
[reply]
[d/l]
Re: Items in Order
by artist (Parson) on Dec 11, 2002 at 23:06 UTC
    Hi,
    I appreciate the responses and making my question more clear, as needed from the assumption in the responses made. All the data I have provided is correct, requires a bit clarification though. 
    Ordered Array: (1,2,3,8,4,5,6)
    I know that 8 is there in the middle and it is correct. It is just a sample of some items which are represented by let's say symbols (here integer numbers) and the provided is let's say the current order of items arrangements. 
    Given Array: (2,1,4,3,5)
    Looking at the common maximum length 'ordered subsets' of both the array. 
    (2,3,5)
(1,3,5)  
(2,4,5)  
(1,4,5)
    Thus maximum length subset I can find here is '3' and above 4 are such subsets.
    I am looking for answer such as length '3' and above found subsets. '3' is part of the answer here and not the input.
    Other Subsets could be: 
    (1,2,3,8,5)
(1,2,8,4,6)
    etc.. But it's not part of the given array.
    Other sets such as 
    (1,4)
(8,6)
(2,3)
    Are there and is also part of the given array but small in length (2) compared to what we found earlier.
    It's really not an attempt to find the max length of increasing integers slice as answered. (Thanks for the attention)
    I hope it makes sense now.

    Thanks,
    Artist

[reply]

      This returns all maximal ordered subsets: 

      sub MaxOrderedSubList {
    my @order= @{ shift @_ };
    my %order;
    @order{@order}= 0..$#order;
    my @list= @{ shift @_ };
    my @wins= ( [] );
    my @idx= ( -1 );
    my $i= 0;
    while(  1  ) {
        do {
            ++$idx[$i];
            if(  $#list < $idx[$i]  ) {
                if(  --$i < 0  ) {
                    return @wins;
                }
                redo;
            }
        } while(  0 < $i
            &&  $order{$list[$idx[$i]]}
                    <= $order{$list[$idx[$i-1]]}  );
        if(  $#{$wins[0]} <= $i  ) {
            @wins= ()   if  $#{$wins[0]} < $i;
            push @wins, [ @list[@idx[0..$i]] ];
        }
        $idx[$i+1]= $idx[$i];
        ++$i;
    }
}

for my $win (  MaxOrderedSubList(
    [1,2,3,8,4,5,6], [2,1,3,5,4] )
) {
    print "@$win\n";
}

for my $win (  MaxOrderedSubList(
    [qw( t h i s w o r k a )], [qw( w h a t i s o k )] )
) {
    print "@$win\n";
}

      [download]
      Output: 
      2 3 5
2 3 4
1 3 5
1 3 4
h i s o k
t i s o k

      [download]
      The maximum size for ordered subsets would be 0 + @{( MaxOrderedSubList( [...], [...] ) )[0]} (updated)

              - tye
[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom