view release on metacpan or  search on metacpan

SetCovering.pm  view on Meta::CPAN

    for my $row (@{$self->{rows}}) {
        my $rowhash = {};
        for(my $i=0; $i<@columns_to_cover; $i++) {
            $rowhash->{$i}++ if $columns_to_cover[$i] and $row->[$i];
        }
        push @hashed_rows, $rowhash;
        DEBUG("Hash of idx (", join('-', keys %$rowhash), ")");
    }

    my %not_covered = %column_hash;

    do {
            # Get the longest list
        my $max_len  = 0;
        my @max_keys = ();
        my $max_idx  = 0;
        for my $idx (0..$#hashed_rows) {
            my $row = $hashed_rows[$idx];
            my @keys = keys %$row;
            if(scalar @keys > $max_len) {

SetCovering.pm  view on Meta::CPAN

                $max_len  = scalar @keys;
                $max_idx  = $idx;
            }
        }

        # Return empty solution if rows can't cover columns_to_cover
        return () unless $max_len;
  
        DEBUG("Removing max_keys: @max_keys");

        delete $not_covered{$_} for @max_keys;
        push @result, $max_idx;

            # Remove max_keys columns from all keys
        foreach my $row (@hashed_rows) {
            delete $row->{$_} for @max_keys;
            DEBUG("Remain (", join('-', keys %$row), ")");
        }
 
        DEBUG("Not covered: (", join('-', keys %not_covered), ")");
        
    } while(scalar keys %not_covered);

    return @result;
}
    
1;

__END__

=head1 NAME