Information Technology Reference
In-Depth Information
Outline of densevec
densevec
1. Input: a set
S
of integers and a length
n
. It is assumed that the members of
S
all lie in
.
2. Create a vector
V
of length
n
. Initialize all elements to be 0.
3. Loop: For each
j
{
1
,...,
n
}
∈
S
,setthe
j
th element of
V
to be 1.
4. Return
V
.
densevec[spvec
,
len ]:=Module[
densevec[spvec
,
len ]:=Module[
{
}
]
},
Do[vec[[spvec[[
j
]]]] = 1
,{
{
{
vec = Tab le[0
,
vec = Tab le[0
,{
vec = Tab le[0
,{
{
len
len
len
}
]
},
}
]
}
,
Do[vec[[spvec[[
j
]]]] = 1
,
Do[vec[[spvec[[
j
]]]] = 1
,{
{
j
,
Length[spvec]
j
,
Length[spvec]
}
];
j
,
Length[spvec]
}
];
}
];
vec]
We now apply this function to each member of our set of subsets, that is, make a dense
representation of each subset.
mat = Map[densevec[#
,
64]&
,
subsets];
It might not be obvious what we have done, so we illustrate using the fourth of our
64 matrix rows.
mat[[4]]
{
1
,
0
,
1
,
1
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
1
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
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
,
1
,
0
,
0
,
0
}
We have ones at positions that correspond to the elements contained in our fourth subset,
and zeros elsewhere. Specifically, the ones are at the positions shown below.
Flatten[Position[mat[[4]]
,
1]]
{
1
,
3
,
4
,
5
,
13
,
29
,
61
}
But this is, up to ordering, exactly the elements in the fourth subset. That is, we pass a
basic consistency check.
Sort[subsets[[4]]]
{
1
,
3
,
4
,
5
,
13
,
29
,
61
}
As in our last knapsack problem, we again work with binary variables and minimize
their sum, subject to certain constraints. We use a binary variables to represent each
subset. A one means we use that subset in our set cover, and a zero means we do not.
Search WWH ::
Custom Search