Information Technology Reference
In-Depth Information
{
22 , 21 , 23 , 19 , 27 , 11 , 43
}
,
{
23 , 24 , 22 , 18 , 26 , 10 , 42
}
,
{
24 , 23 , 21 , 17 , 25 , 9 , 41
}
,
{
{
22 , 21 , 23 , 19 , 27 , 11 , 43
22 , 21 , 23 , 19 , 27 , 11 , 43
}
}
,
,
{
{
23 , 24 , 22 , 18 , 26 , 10 , 42
23 , 24 , 22 , 18 , 26 , 10 , 42
}
}
,
,
{
{
24 , 23 , 21 , 17 , 25 , 9 , 41
24 , 23 , 21 , 17 , 25 , 9 , 41
}
}
,
,
{
25 , 26 , 28 , 32 , 24 , 8 , 40
},{
26 , 25 , 27 , 31 , 23 , 7 , 39
},{
27 , 28 , 26 , 30 , 22 , 6 , 38
},
{
{
25 , 26 , 28 , 32 , 24 , 8 , 40
25 , 26 , 28 , 32 , 24 , 8 , 40
}
}
,
,
{
{
26 , 25 , 27 , 31 , 23 , 7 , 39
26 , 25 , 27 , 31 , 23 , 7 , 39
}
}
,
,
{
{
27 , 28 , 26 , 30 , 22 , 6 , 38
27 , 28 , 26 , 30 , 22 , 6 , 38
}
}
,
,
{
28 , 27 , 25 , 29 , 21 , 5 , 37
},{
29 , 30 , 32 , 28 , 20 , 4 , 36
},{
30 , 29 , 31 , 27 , 19 , 3 , 35
},
{
{
28 , 27 , 25 , 29 , 21 , 5 , 37
28 , 27 , 25 , 29 , 21 , 5 , 37
}
}
,
,
{
{
29 , 30 , 32 , 28 , 20 , 4 , 36
29 , 30 , 32 , 28 , 20 , 4 , 36
}
}
,
,
{
{
30 , 29 , 31 , 27 , 19 , 3 , 35
30 , 29 , 31 , 27 , 19 , 3 , 35
}
}
,
,
{
31 , 32 , 30 , 26 , 18 , 2 , 34
},{
32 , 31 , 29 , 25 , 17 , 1 , 33
},{
33 , 34 , 36 , 40 , 48 , 64 , 32
},
{
{
31 , 32 , 30 , 26 , 18 , 2 , 34
31 , 32 , 30 , 26 , 18 , 2 , 34
}
}
,
,
{
{
32 , 31 , 29 , 25 , 17 , 1 , 33
32 , 31 , 29 , 25 , 17 , 1 , 33
}
}
,
,
{
{
33 , 34 , 36 , 40 , 48 , 64 , 32
33 , 34 , 36 , 40 , 48 , 64 , 32
}
}
,
,
{
{
{
34 , 33 , 35 , 39 , 47 , 63 , 31
34 , 33 , 35 , 39 , 47 , 63 , 31
34 , 33 , 35 , 39 , 47 , 63 , 31
}
}
}
,
,
,
{
{
{
35 , 36 , 34 , 38 , 46 , 62 , 30
35 , 36 , 34 , 38 , 46 , 62 , 30
35 , 36 , 34 , 38 , 46 , 62 , 30
}
}
}
,
,
,
{
{
{
36 , 35 , 33 , 37 , 45 , 61 , 29
36 , 35 , 33 , 37 , 45 , 61 , 29
36 , 35 , 33 , 37 , 45 , 61 , 29
}
}
}
,
,
,
{
{
{
37 , 38 , 40 , 36 , 44 , 60 , 28
37 , 38 , 40 , 36 , 44 , 60 , 28
37 , 38 , 40 , 36 , 44 , 60 , 28
}
}
}
,
,
,
{
{
{
38 , 37 , 39 , 35 , 43 , 59 , 27
38 , 37 , 39 , 35 , 43 , 59 , 27
38 , 37 , 39 , 35 , 43 , 59 , 27
}
}
}
,
,
,
{
{
{
39 , 40 , 38 , 34 , 42 , 58 , 26
39 , 40 , 38 , 34 , 42 , 58 , 26
39 , 40 , 38 , 34 , 42 , 58 , 26
}
}
}
,
,
,
{
{
{
40 , 39 , 37 , 33 , 41 , 57 , 25
40 , 39 , 37 , 33 , 41 , 57 , 25
40 , 39 , 37 , 33 , 41 , 57 , 25
}
}
}
,
,
,
{
{
{
41 , 42 , 44 , 48 , 40 , 56 , 24
41 , 42 , 44 , 48 , 40 , 56 , 24
41 , 42 , 44 , 48 , 40 , 56 , 24
}
}
}
,
,
,
{
{
{
42 , 41 , 43 , 47 , 39 , 55 , 23
42 , 41 , 43 , 47 , 39 , 55 , 23
42 , 41 , 43 , 47 , 39 , 55 , 23
}
}
}
,
,
,
{
{
{
43 , 44 , 42 , 46 , 38 , 54 , 22
43 , 44 , 42 , 46 , 38 , 54 , 22
43 , 44 , 42 , 46 , 38 , 54 , 22
}
},{
},{
,
{
44 , 43 , 41 , 45 , 37 , 53 , 21
44 , 43 , 41 , 45 , 37 , 53 , 21
44 , 43 , 41 , 45 , 37 , 53 , 21
}
},{
},{
,
{
45 , 46 , 48 , 44 , 36 , 52 , 20
45 , 46 , 48 , 44 , 36 , 52 , 20
45 , 46 , 48 , 44 , 36 , 52 , 20
}
},
},
,
{
{
{
46 , 45 , 47 , 43 , 35 , 51 , 19
46 , 45 , 47 , 43 , 35 , 51 , 19
46 , 45 , 47 , 43 , 35 , 51 , 19
}
},{
},{
,
{
47 , 48 , 46 , 42 , 34 , 50 , 18
47 , 48 , 46 , 42 , 34 , 50 , 18
47 , 48 , 46 , 42 , 34 , 50 , 18
}
},{
},{
,
{
48 , 47 , 45 , 41 , 33 , 49 , 17
48 , 47 , 45 , 41 , 33 , 49 , 17
48 , 47 , 45 , 41 , 33 , 49 , 17
}
},
},
,
{
{
{
49 , 50 , 52 , 56 , 64 , 48 , 16
49 , 50 , 52 , 56 , 64 , 48 , 16
49 , 50 , 52 , 56 , 64 , 48 , 16
}
}
}
,
,
,
{
{
{
50 , 49 , 51 , 55 , 63 , 47 , 15
50 , 49 , 51 , 55 , 63 , 47 , 15
50 , 49 , 51 , 55 , 63 , 47 , 15
}
}
}
,
,
,
{
{
{
51 , 52 , 50 , 54 , 62 , 46 , 14
51 , 52 , 50 , 54 , 62 , 46 , 14
51 , 52 , 50 , 54 , 62 , 46 , 14
}
}
}
,
,
,
{
{
{
52 , 51 , 49 , 53 , 61 , 45 , 13
52 , 51 , 49 , 53 , 61 , 45 , 13
52 , 51 , 49 , 53 , 61 , 45 , 13
}
}
}
,
,
,
{
{
{
53 , 54 , 56 , 52 , 60 , 44 , 12
53 , 54 , 56 , 52 , 60 , 44 , 12
53 , 54 , 56 , 52 , 60 , 44 , 12
}
}
}
,
,
,
{
{
{
54 , 53 , 55 , 51 , 59 , 43 , 11
54 , 53 , 55 , 51 , 59 , 43 , 11
54 , 53 , 55 , 51 , 59 , 43 , 11
}
}
}
,
,
,
{
{
{
55 , 56 , 54 , 50 , 58 , 42 , 10
55 , 56 , 54 , 50 , 58 , 42 , 10
55 , 56 , 54 , 50 , 58 , 42 , 10
}
}
}
,
,
,
{
{
{
56 , 55 , 53 , 49 , 57 , 41 , 9
56 , 55 , 53 , 49 , 57 , 41 , 9
56 , 55 , 53 , 49 , 57 , 41 , 9
}
}
}
,
,
,
{
{
{
57 , 58 , 60 , 64 , 56 , 40 , 8
57 , 58 , 60 , 64 , 56 , 40 , 8
57 , 58 , 60 , 64 , 56 , 40 , 8
}
}
}
,
,
,
{
{
{
58 , 57 , 59 , 63 , 55 , 39 , 7
58 , 57 , 59 , 63 , 55 , 39 , 7
58 , 57 , 59 , 63 , 55 , 39 , 7
}
}
}
,
,
,
{
{
{
59 , 60 , 58 , 62 , 54 , 38 , 6
59 , 60 , 58 , 62 , 54 , 38 , 6
59 , 60 , 58 , 62 , 54 , 38 , 6
}
}
}
,
,
,
{
{
{
60 , 59 , 57 , 61 , 53 , 37 , 5
60 , 59 , 57 , 61 , 53 , 37 , 5
60 , 59 , 57 , 61 , 53 , 37 , 5
}
}
}
,
,
,
{
{
{
61 , 62 , 64 , 60 , 52 , 36 , 4
61 , 62 , 64 , 60 , 52 , 36 , 4
61 , 62 , 64 , 60 , 52 , 36 , 4
}
}
}
,
,
,
{
{
{
62 , 61 , 63 , 59 , 51 , 35 , 3
62 , 61 , 63 , 59 , 51 , 35 , 3
62 , 61 , 63 , 59 , 51 , 35 , 3
}
}
}
,
,
,
{
{
{
63 , 64 , 62 , 58 , 50 , 34 , 2
63 , 64 , 62 , 58 , 50 , 34 , 2
63 , 64 , 62 , 58 , 50 , 34 , 2
}
}
}
,
,
,
{
{
{
64 , 63 , 61 , 57 , 49 , 33 , 1
64 , 63 , 61 , 57 , 49 , 33 , 1
64 , 63 , 61 , 57 , 49 , 33 , 1
}}
}}
}}
;
;
;
We do a brief check that the union of the subset elements is indeed the set of integers
from 1 through 64.
Union[Flatten[subsets]] == Range[64]
True
4.5.1
An Ad Hoc Approach to Subset Covering
We will set up our objective function as follows. We represent a set of 12 subsets of this
master set by a set of 12 integers in the range from 1 to the number of subsets (which
in this example is, coincidently, also 64). This set is allowed to contain repetitions. Our
objective function to minimize will be based on how many elements from 1 through 64
are “covered”. Specifically it will be 2 raised to the #(elements not covered) power. The
code below does this.
Outline of scfun
scfun
1. Input: a vector V of integers, a set S of subsets, and an integer n to denote the
range of integers
.
2. Compute U , the union of elements contained in the subsets S j ,forall j
{
1 ,..., n
}
V .
3. Calculate c , the cardinality of the complement of our initial range by U .
More succinctly this is
|{
1 ,..., n
}−
U
|
, where subtraction is taken to mean
set complement ,and
|
S
|
denotes the cardinality of S .
4. Return 2 c .
scfun[ n :
scfun[ n :
scfun[ n :
, set , mx Integer]:=
2 Length[Complement[Range[mx] , Union[Flatten[set[[ n ]]]]]]
{
{
{
Integer
Integer
Integer
}
}
}
, set , mx Integer]:=
, set , mx Integer]:=
2 Length[Complement[Range[mx] , Union[Flatten[set[[ n ]]]]]]
Search WWH ::




Custom Search