The Perl and Raku Conference 2025: Greenville, South Carolina - June 27-29 Learn more

MSCHILLI / Algorithm-SetCovering-0.05 / README 

            

              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

              
######################################################################
    Algorithm::SetCovering 0.05
######################################################################
NAME
    Algorithm::SetCovering - Algorithms to solve the "set covering problem"
SYNOPSIS
        use Algorithm::SetCovering;
        my $alg = Algorithm::SetCovering->new(
            columns => 4,
            mode    => "greedy");
        $alg->add_row(1, 0, 1, 0);
        $alg->add_row(1, 1, 0, 0);
        $alg->add_row(1, 1, 1, 0);
        $alg->add_row(0, 1, 0, 1);
        $alg->add_row(0, 0, 1, 1);
        my @to_be_opened = (@ARGV || (1, 1, 1, 1));
     
        my @set = $alg->min_row_set(@to_be_opened);
     
        print "To open (@to_be_opened), we need ",
              scalar @set, " keys:\n";
        for(@set) {
            print "$_: ", join('-', $alg->row($_)), "\n";
        }
DESCRIPTION
    Consider having M keys and N locks. Every key opens one or more locks:
             | lock1 lock2 lock3 lock4
        -----+------------------------
        key1 |   x           x
        key2 |   x     x
        key3 |   x     x     x
        key4 |         x           x
        key5 |               x     x
    Given an arbitrary set of locks you have to open (e.g. 2,3,4), the task
    is to find a minimal set of keys to accomplish this. In the example
    above, the set [key4, key5] fulfils that condition.
    The underlying problem is called "set covering problem" and the
    corresponding decision problem is NP-complete.
  Methods
    $alg = Algorithm::SetCovering->new(columns => $cols, [mode => $mode]);
        Create a new Algorithm::SetCovering object. The mandatory parameter
        "columns" needs to be set to the number of columns in the matrix
        (the number of locks in the introductory example).
        "mode" is optional and selects an algorithm for finding the
        solution. The following values for "mode" are implemented:
        "brute_force"
            Will iterate over all permutations of keys. Only recommended for
            very small numbers of keys.
        "greedy"
            Greedy algorithm. Scales O(mn^2). Can't do much better for a
            NP-hard problem.
        The default for "mode" is set to "greedy".
    $alg->add_row(@columns)
        Add a new row to the matrix. In the example above, this adds one key
        and specifies which locks it is able to open.
            $alg->add_row(1,0,0,1);
        specifies that the new key can open locks #1 and #4.
        The number of elements in @columns needs to match the previously
        defined number of columns.
    $alg->min_row_set(@columns_to_cover)
        Determines a minimal set of keys to cover a given set of locks and
        returns an array of index numbers for those keys.
        Defines which columns have to be covered by passing in an array with
        true values on element positions that need to be covered. For
        example,
            my @idx_set = $alg->min_row_set(1,1,0,1);
        specifies that all but the third column have to be covered and
        returns an array of index numbers into an array, defined previously
        (and implicitely) via successive add_row() commands.
        If no set of keys can be found that satisfies the given requirement,
        an empty list is returned.
        If you've forgotten which locks the key referred to by a certain
        index number can open, use the "rows()" method to find out:
            my(@opens_locks) = $alg->rows($idx_set[0]);
        will give back an array of 0's and 1's, basically returning the very
        parameters we've passed on to the add_row() command previously.
  Strategies
    Currently, the module implements the Greedy algorithm and also (just for
    scientific purposes) a dumb brute force method, creating all possible
    combinations of keys, sorting them by the number of keys used
    (combinations with fewer keys have priority) and trying for each of them
    if it fits the requirement of opening a given number of locks.
    This obviously won't scale beyond a really small number of keys (N),
    because the number of permutations will be 2**N-2.
    The Greedy Algorithm, on the other hand scales with O(mn^2), with m
    being the number of keys and n being the number of locks.
  Limitations
    Julien Gervais-Bird <j.bird@usherbrooke.ca> points out: The greedy
    algorithm does not always return the minimal set of keys. Consider this
    example:
             | lock1 lock2 lock3 lock4 lock5 lock6
        -----+------------------------------------
        key1 |   x           x           x
        key2 |   x     x
        key3 |               x     x
        key4 |                           x     x
    The minimal set of keys to open all the locks is (key2, key3, key4),
    however the greedy algorithm will return (key1,key2,key3,key4) because
    key1 opens more locks than any other key.
AUTHOR
    Mike Schilli, 2003, <m@perlmeister.com>
    Thanks to the friendly guys on rec.puzzles, who provided me with
    valuable input to analyze the problem and explained the algorithm:
        Craig <c_quest000@yahoo.com>
        Robert Israel <israel@math.ubc.ca>
        Patrick Hamlyn <path@multipro.n_ocomsp_am.au>
COPYRIGHT AND LICENSE
    Copyright 2003 by Mike Schilli
    This library is free software; you can redistribute it and/or modify it
    under the same terms as Perl itself.