Information Technology Reference
In-Depth Information
This may be a bit elusive. We will examine its behavior on a specific set of subsets.
Suppose we take the first 12 of our subsets.
first12 = Take[subsets
,
12]
{{
1
,
2
,
4
,
8
,
16
,
32
,
64
}
,
{
2
,
1
,
3
,
7
,
15
,
31
,
63
}
,
{
3
,
4
,
2
,
6
,
14
,
30
,
62
}
,
{
4
,
3
,
1
,
5
,
13
,
29
,
61
}
,
{
5
,
6
,
8
,
4
,
12
,
28
,
60
}
,
{
6
,
5
,
7
,
3
,
11
,
27
,
59
}
,
{
7
,
8
,
6
,
2
,
10
,
26
,
58
}
,
{
8
,
7
,
5
,
1
,
9
,
25
,
57
}
,
{
9
,
10
,
12
,
16
,
8
,
24
,
56
}
,
{
10
,
9
,
11
,
15
,
7
,
23
,
55
}
,
{
11
,
12
,
10
,
14
,
6
,
22
,
54
}
,
{
12
,
11
,
9
,
13
,
5
,
21
,
53
}}
Their union is
elementsinfirst12 = Union[Flatten[first12]]
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
10
,
11
,
12
,
13
,
14
,
15
,
16
,
21
,
22
,
23
,
24
,
25
,
26
,
27
,
28
,
29
,
30
,
31
,
32
,
53
,
54
,
55
,
56
,
57
,
58
,
59
,
60
,
61
,
62
,
63
,
64
}
Our objective function for this set of subsets raises 2 to the power that is the cardinality
of the set of integers 1 through 64 complemented by this set. So how many elements
does this union miss?
missed = Complement[Range[64]
,
elementsinfirst12]
{
17
,
18
,
19
,
20
,
33
,
34
,
35
,
36
,
37
,
38
,
39
,
40
,
41
,
42
,
43
,
44
,
45
,
46
,
47
,
48
,
49
,
50
,
51
,
52
}
Length[missed]
24
2
∧
Length[missed]
16777216
Does this agree with the function we defined above? Indeed it does.
scfun[Range[12]
,
subsets
,
64]
16777216
We now give outline and code to find a set of spanning subsets.
Outline of spanningSets
spanningSets
1. Input: a set
S
of
m
subsets, an integer
k
specifying how many we are to use for
our cover, and option values to pass to
NMinimize
. We assume the union of
all subsets covers some range
{
1
,...,
n
}
.
2. Create a vector of
k
variables.
Search WWH ::
Custom Search