Information Technology Reference
In-Depth Information
Let us consider the vector of those zeros and ones. Now our requirement is that we fully
cover the superset, that is, the range of integers from 1 to 64.
How might we impose this? Well, let us take a look at the dot product of such a vec-
tor with the matrix of bit vectors that we already formed. Again we use as an example
the first 12 subsets, so our vector representing this has ones in the first 12 slots, and
zeros in the remaining 64-12=52 slots.
first12vec = Join[ConstantArray[1
,
12]
,
ConstantArray[0
,
52]]
{
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
}
What does the dot product of this vector with our matrix of bit vectors represent? Well,
let's consider the meaning of this matrix for a moment. A one in row
j
, column
k
means that subset
j
contains element
k
. One then realizes that the dot product gives
us the following information. The
k
th element in the result will be a nonnegative num-
ber (possibly zero), and represent the number of times that
k
appears in the union of
subsets represented by
first12vec
. So the condition we will need to impose in our
optimization is that the dot product of this vector with our matrix of bitvectors has all
positive entries. Notice that
first12vec
fails to satisfy this condition.
first12vec
.
mat
{
4
,
4
,
4
,
4
,
5
,
5
,
5
,
5
,
4
,
4
,
4
,
4
,
2
,
2
,
2
,
2
,
0
,
0
,
0
,
0
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
}
Outline of spanningSets2
spanningSets2
1. Input: a set
S
of
m
subsets (each now represented as a bit vector), and option
values to pass to
NMinimize
. We assume the union of all subsets covers
some range
.
2. Create a vector of
m
variables,
vars
.
3. Set up constraints.
All variables lie between 0 and 1.
All variables are integer valued.
The union of subsets corresponding to variables with value of 1 covers the
full range
{
1
,...,
n
}
.
This is done by checking that each elements of
S
.vars is
greater or equal to 1.
4. Call
NMinimize
to minimize the sum of vars, subject to the above con-
straints, using the input option settings.
5. Return the minimal value and the list of positions denoting which subsets we
used in the cover.
{
1
,...,
n
}
Search WWH ::
Custom Search