Information Technology Reference
In-Depth Information
For example,
U
3,3
=
{
}
,
U
1,2
=
{
}
,and
U
2,1
=
{
}
24, 25, 26, 27, 29, 30, 31
4, 5, 6, 7
4, 5
.
The set
U
a
,
b
has size 2
b
.
For
n
=
2
s
,everyset
D
i
=
(
n
)
−{
i
}
can be represented as the disjoint union of the
2
s−j
sets
U
a
,
b
below, where 0
≤
a
i
,
j
≤
−
1. (This is the complementary number system;
see Fig.
9.14
.)
D
i
=
U
a
i
,
s
−
1
,
s−
1
∪
U
a
i
,
s
−
2
,
s−
2
∪···∪
U
a
i
,0
,0
To see this, note that if
i
is in the first (second) half of
(
n
)
,
U
a
i
,
s
−
1
,
s−
1
denotes the second
(first) half; that is,
a
i
,
s−
1
=
1(
a
i
,
s−
1
=
0). The next set,
U
a
i
,
s
−
2
,
s−
2
, is the half of the
remaining set
D
i
−
U
a
i
,
s
−
1
,
s−
1
that does not contain
i
,etc.Thus,
D
i
is decomposed as
the disjoint union of sets of size 2
s−
1
,2
s−
2
,
...
,2
0
For example, when
n
=
16,
D
3
=
U
1,3
∪
U
1,2
∪
U
0,1
∪
U
2,0
.Figure
9.14
shows the values of
a
i
,
s−
1
,
a
i
,
s−
2
,
...
,
a
i
,0
for each
i
∈
(
n
)
for
n
=
8.
As suggested in Fig.
9.14
,thesets
{
D
i
|
i
∈
(
n
)
}
have either
U
0,
s−
1
or
U
1,
s−
1
in
common. Similarly, they also have either
U
1,
s−
1
∪
U
1,
s−
2
,
U
0,
s−
1
∪
U
1,
s−
2
,
U
3,
s−
1
∪
U
0,
s−
2
,
or
U
2,
s−
1
∪
U
0,
s−
2
in common. Continuing in this fashion, we construct the sets
{
D
i
|
i
∈
by successively forming the disjoint union of 2
j
s
. Assembling the
sets in this fashion is much more economical than assembling them individually.
The value of
τ
(
n
)
k
,
(
n
)
}
sets, 1
≤
j
≤
(
n
)
,isthe
k
th largest variable whose index is in
D
i
.Fromnow
on we equate the variables with their indices. Sorting the sets into which
D
i
is decomposed
simplifies the computation. But these sets are exactly the sets that are sorted by Batcher's
sorting network based on Batcher's merging algorithm. (See Theorem
6.8.3
.) Since on
Boolean data a comparator consists of one
AND
for the max operation and one
OR
for the
min operation, a monotone circuit of size
O
(
n
log
2
n
)
exists to sort the sets
¬i
,
i
∈
{
U
i
,
j
|
≤
i
≤
0
2
s−j
−
≤
j
≤
s
−
}
1, 0
1
.
The functions
τ
(
n
)
≤
i
≤
n
−
{
U
i
,
j
|
≤
i
≤
k
,
¬i
,0
1, can be obtained by sorting the sets
0
2
s−j
(
n
)
, as suggested
above, and then taking the
k
th largest element. A faster way merges the sorted versions of
the sets
U
a
i
,
s
−
1
,
s−
1
,
U
a
i
,
s
−
2
,
s−
2
,
...
,
U
a
i
,0
,0
in the order in which
D
i
is assembled above.
For each of these sets the sorting network presents its elements in sorted order.
−
≤
j
≤
s
−
}
, merging them in groups to form
D
i
for
i
∈
1, 0
1
i
a
i
,0
a
i
,1
a
i
,2
0
1
1
1
1
0
1
1
2
3
0
1
3
2
0
1
4
5
3
0
5
4
3
0
6
7
2
0
7
6
2
0
Figure 9.14
The coefficients
a
i
,
j
of
D
i
=
(
n
)
−{i}
in the expansion
U
a
i
,
s
−
1
,
s−
1
∪
U
a
i
,0
,0
for
n
=
2
s
U
a
i
,
s
−
2
,
s−
2
∪···∪
=
8and
s
=
3.
Search WWH ::
Custom Search