Re: Subsets and adjacent values

As much as I am chuffed that you're using a module I wrote, I'm afraid there's a much easier way of doing this. Just set down a marker at the beginnning of the list, move the right marker down as far as the shortest length of subset you want, and then start pushing out out the subsets as you move to the end of the string. When you get to the end, move the beginning marker one to right, and repeat while you can continue to squeeze out a subset. Then stop.

Programmatically, this gives:

my @set = ('A' .. 'Z', 0 .. 3);
my $min = 3;

my @result;

for my $begin (0 .. $#set-$min+1) {
    for my $end ($begin+$min-1 .. $#set) {
        push @result, "@set[$begin .. $end]";
    }
}

{
    local $" = ''; # interpolate an array without spaces
    print "$_\n" for @result;
}
[download]

This will be really, really fast. If you try your approach on a powerset of 30 elements your program will still be running after the heat-death of the universe.

update: oops, BrowkerUK beat me to it. That'll teach me to get side-tracked into a conversation in real life and leave the form in preview mode. Still, it's interesting to compare the two techniques: he chose start postition and length, I chose start and end positions. Pick your poison :)

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

Comment on Re: Subsets and adjacent values Download Code

Replies are listed 'Best First'.

Re^2: Subsets and adjacent values
by andreas1234567 (Vicar) on May 30, 2008 at 16:19 UTC

Data::PowerSet

$ diff -ubB PowerSet.pm.org PowerSet.pm 
--- PowerSet.pm.org    2008-05-30 11:22:31.000000000 +0200
+++ PowerSet.pm    2008-05-30 12:46:32.000000000 +0200
@@ -9,7 +9,7 @@
 use Exporter;
 
 use vars qw/$VERSION @ISA @EXPORT_OK/;
-$VERSION = '0.05';
+$VERSION = '0.06';
 @ISA     = ('Exporter');
 
 =head1 NAME
@@ -18,8 +18,8 @@
 
 =head1 VERSION
 
-This document describes version 0.05 of Data::PowerSet, released
-2008-05-13.
+This document describes version 0.06 of Data::PowerSet, released
+2008-05-30.
 
 =head1 SYNOPSIS
 
@@ -161,6 +161,22 @@
 When this attribute is used, the C<next()> method will
 return a scalar rather than a reference to an array.
 
+=item B<adjacent>
+
+When this attribute is used, the returned list will contain adjacent
+elements only. E.g. 
+
+  my $ps = Data::PowerSet->new( {min=>3, adjacent=>1}, 2, 3, 5, 8, 11
+ );
+
+will produce
+
+  2, 3, 5, 8, 11
+  2, 3, 5, 8
+  3, 5, 8, 11
+  2, 3, 5
+  3, 5, 8
+  5, 8, 11
+
 =back
 
 =cut
@@ -195,6 +211,13 @@
 
     ($args{min}, $args{max}) = ($args{max}, $args{min})
         if $args{max} < $args{min};
+
+    $args{adjacent} =
+            exists $args{adjacent}
+                ? $args{adjacent} 
+                : 0
+        ;
+
     return bless \%args, $class;
 }
 
@@ -217,9 +240,18 @@
         return undef unless $self->{current} >= 0;
         my $mask   = $self->{current}--;
         my $offset = 0;
+                my $last   = -1;
         @set = ();
         while( $mask ) {
+                    if ($self->{adjacent}) {
+                        if ($mask & 1 && (($offset-1 == $last) || sca
+lar(@set) == 0)) {
+                            $last = $offset;
+                            push @set, $self->{data}[$offset];
+                        }
+                    } else {
             push @set, $self->{data}[$offset] if $mask & 1;
+                    }
+
             $mask >>= 1;
             ++$offset;
         }
[download]

--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

[reply]
[d/l]


Welcome to the Monastery
	PerlMonks