in reply to Generating powerset with progressive ordering
I had an easier time thinking of this as manipulating the characteristic sequence of the subsets (i.e, a string of 0's and 1's, where the first bit is a 1 if the first factor is included in the subset, etc). If you look at the characteristic sequences given in your example, you can see that there are three rules being applied (you can print out $str to see what's going on under the covers). Anyway, this code does its manipulations on the characteristic sequence and converts it to the appropriate subset:
I'd be interested to see this simplified a bit. I know you mentioned in the CB that tye had an idea for a solution, and I wonder if he's able to implement it with manipulations to the subsets themselves instead of their characteristic sequences.sub iter { my @factors = @_; my $str; return sub { if (not defined $str) { $str = "1" . ("0" x $#factors); return map { substr($str, $_, 1) ? $factors[$_] : () } 0 .. $#factors; } for ($str) { s/0(0*)$/1$1/ or s/11$/01/ or s/^(.*)10(.*)$/"${1}01" . "0" x length $2/e or return; } return map { substr($str, $_, 1) ? $factors[$_] : () } 0 .. $#factors; }; } my $i = iter( 2, 3, 5, 7 ); while (my @s = $i->()) { print "@s\n"; } __END__ 2 2 3 2 3 5 2 3 5 7 2 3 7 2 5 2 5 7 2 7 3 3 5 3 5 7 3 7 5 5 7 7
You also mentioned wanting to know when the "next phase" of iterations began (the horizontal lines in your example). You can figure this out by checking which substitution rule was actually applied.
Update: Here is the code with the "next phase" markers:
sub iter { my @factors = @_; my $str; my $break = 0; return sub { if (not defined $str) { $str = "1" . ("0" x $#factors); return map { substr($str, $_, 1) ? $factors[$_] : () } 0 .. $#factors; } for ($str) { s/0(0*)$/1$1/ and last; return "BREAK" if $break = !$break; s/11$/01/ or s/^(.*)10(.*)$/"${1}01" . "0" x length $2/e or return; } return map { substr($str, $_, 1) ? $factors[$_] : () } 0 .. $#factors; }; } my $i = iter( 2, 3, 5, 7 ); while (my @s = $i->()) { print "@s\n"; } __END__ 2 2 3 2 3 5 2 3 5 7 BREAK 2 3 7 BREAK 2 5 2 5 7 BREAK 2 7 BREAK 3 3 5 3 5 7 BREAK 3 7 BREAK 5 5 7 BREAK 7 BREAK
blokhead
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Generating powerset with progressive ordering
by fizbin (Chaplain) on Feb 25, 2005 at 19:43 UTC | |
Re^2: Generating powerset with progressive ordering
by Limbic~Region (Chancellor) on Feb 25, 2005 at 20:46 UTC | |
by Roy Johnson (Monsignor) on Apr 26, 2005 at 20:20 UTC | |
by tlm (Prior) on Apr 26, 2005 at 23:46 UTC | |
by Roy Johnson (Monsignor) on Apr 27, 2005 at 02:38 UTC |
In Section
Seekers of Perl Wisdom