关于无穷这个词的意义
有人说:
数学家们不可能谈论由无限符号刻画的数学系统的存在性,那是幻觉:)由有限个符号(哪怕它包含无限符号)刻画的系统仍然是有限的。
问题在于语言,就出在“无限”这个名词上,假设我们换个名字,其实就会发现,它跟其他的符号没有任何区别。我们误以为包含“无限”这个符号的语言所描绘的那个假设的存在是无限的,但实际上根本不是。
我猜想,无限应该是人脑对一些序列进行归纳的产物。所谓实无穷潜无穷之争,无非是这个无穷符号的运算规则之争,如果扯到假设的那个无限存在之争,就永远扯不清了。
持这种观点的人显然没有弄清楚无穷这个术语的含义是怎么规定出来的。只要规定:『0是自然数,任何自然数的后继是自然数,0不是任何自然数的后继,任何两个不同自然数的后继也不同』那么任何满足这四条规定(连归纳公理都用不着)的集合的元素就一定无法一一映射到任何有限个元素的集合上,而任何有限集合却能够一一映射到该集合的某个子集上。这种性质当然可以不起名叫『无穷』,但无论如何这种性质不是任何有限集合所具有的,无论给这种性质起个什么名字,这种性质本身都是特殊的。纠缠于这种性质是否能够命名为『无穷』,纯属吃饱了撑的。
Reinvent wheels, my quick sort implementation, just for fun
Not deeply optimized.
The depth of the recursion is restricted , because the recursion is only performed for the partition with less element. Even under the worst case, the stack depth will still be under control.
Tail recursion is eliminated.
Brief explanation:
[cc lang=”cpp”]
initial state:
p<<< #
p=== #
| p>>>
p… |
|—————————————–|
……………………………………#
state after choosing the pivot:
p<<< #
p=== #
| p>>>
|p… |
||—————————————-|
=…………………………………..#
the middle state during partitioning:
p<<< #
| p=== #
| | p>>> #
| | p… | #
|——–|———|—————-|—–#
<<<<<<<<<==========.................>>>>>>#
the final state after partition:
p<<< #
| p=== #
| | p>>> #
| | p… #
|—————|—————|———#
<<<<<<<<<<<<<<<<================>>>>>>>>>>#
Then, recurse.
[/cc]
Pointer “p<<<" points to the begining of the "<<<" area in which each element is preceding to the pivot.
Pointer "p===" points to the begining of the "===" area in which each element is equivalent to the pivot.
Pointer "p>>>” points to the begining of the “>>>” area in which each element is succeeding to the pivot.
Pointer “p…” points to the begining of the “…” area in which each element is unprocessed.
The code:
[cc lang=”cpp”]
template
class QuickSort {
public:
static void sort(Elem pp[], size_t n) {
Elem *pe, *pu, *ps;
// pp:”p<<<", pe:"p===", ps:"p>>>”, pu:”p…”
do {
// recursion exit, use other sort algorithm to process small array
// recommendation: use sorting network algorithm when array size less than 9
if(n < Cutoff) {
ShortSort
return;
}
pe = pp;
pu = pp;
ps = pp+n;
// choosing pivot
swap(pe, pivot(pp, n));
pu++;
// partitioning
while(pu < ps) {
while((*pe == *pu) && (pu < ps)) ++pu;
while((*pe < *pu) && (pu < ps)) {
--ps;
swap(pu, ps);
}
while((*pu < *pe) && (pu < ps)) {
swap(pe, pu);
++pe;
++pu;
}
}
// recursion only for the partition with less elements
if((pe - pp) < (n - (ps - pp))) {
sort(pp, pe - pp);
n = n - (ps - pp);
pp = ps;
} else {
sort(ps, n - (ps - pp));
n = pe - pp;
}
// tail recursion elimination
} while(true);
}
private:
static Elem *pivot(Elem pp[], size_t n) {
if(n < 10) return pp + n/2;
else return pp + random(n);
// random(n) should return a uniformly distributed random number in [0, n)
}
};
[/cc]
Finding all paths from source to destination
[cc lang=”cpp”]
stack node_stack;
set node_set;
AllPathFromSourceToDestination(node s, node d) {
node_stack.push(s);
node_set.add(s); //mark each node in the path
// for each node v that adjacent with node s:
for_each(node v, adjacent(v,s)) {
if(v == d) {
Output(node_stack);
} else {
if(node_set.has(v)==false) {
AllPathFromSourceToDestination(v, d);
}
}
}
node_set.del(s);
node_stack.pop(s);
}
[/cc]
Sorting network
The following is network-sorting algorithm for less than 33 elements.
What is Sorting Network? Wiki: sorting network
List of sorting networks:
From: sorting networks
Input the number n (maximum 32)
Algorithm choices: “Best”
Click [Take a look] button.
—————————
Zero-one principle
While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially when they are larger. However, because of the so-called zero-one principle, far fewer trials are in fact needed to test the validity of a sorting network.
The zero-one principle states that a sorting network is valid if it can sort all 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of the Bouricius’s Theorem in 1954 by W. G. Bouricius.
[cc lang=”cpp”]
static const unsigned int network02[][2] = {
{ 0, 1},
};
static const unsigned int network03[][2] = {
{ 1, 2},
{ 0, 2},
{ 0, 1},
};
static const unsigned int network04[][2] = {
{ 0, 1}, { 2, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network05[][2] = {
{ 0, 1}, { 3, 4},
{ 2, 4},
{ 2, 3}, { 1, 4},
{ 0, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network06[][2] = {
{ 1, 2}, { 4, 5},
{ 0, 2}, { 3, 5},
{ 0, 1}, { 3, 4}, { 2, 5},
{ 0, 3}, { 1, 4},
{ 2, 4}, { 1, 3},
{ 2, 3},
};
static const unsigned int network07[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6},
{ 0, 2}, { 3, 5}, { 4, 6},
{ 0, 1}, { 4, 5}, { 2, 6},
{ 0, 4}, { 1, 5},
{ 0, 3}, { 2, 5},
{ 1, 3}, { 2, 4},
{ 2, 3},
};
static const unsigned int network08[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7},
{ 1, 5}, { 2, 6},
{ 1, 4}, { 3, 6},
{ 2, 4}, { 3, 5},
{ 3, 4},
};
static const unsigned int network09[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7},
{ 1, 2}, { 4, 5}, { 7, 8},
{ 0, 1}, { 3, 4}, { 6, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 8},
{ 3, 6}, { 4, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 7}, { 2, 6},
{ 1, 3}, { 4, 6},
{ 2, 4}, { 5, 6},
{ 2, 3},
};
static const unsigned int network10[][2] = {
{ 4, 9}, { 3, 8}, { 2, 7}, { 1, 6}, { 0, 5},
{ 1, 4}, { 6, 9}, { 0, 3}, { 5, 8},
{ 0, 2}, { 3, 6}, { 7, 9},
{ 0, 1}, { 2, 4}, { 5, 7}, { 8, 9},
{ 1, 2}, { 4, 6}, { 7, 8}, { 3, 5},
{ 2, 5}, { 6, 8}, { 1, 3}, { 4, 7},
{ 2, 3}, { 6, 7},
{ 3, 4}, { 5, 6},
{ 4, 5},
};
static const unsigned int network11[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 1, 3}, { 5, 7}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 3, 7},
{ 1, 5}, { 6,10}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network12[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11},
{ 1, 3}, { 5, 7}, { 9,11}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 7,11},
{ 1, 5}, { 6,10}, { 3, 7}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 7,11}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network13[][2] = {
{ 1, 7}, { 9,11}, { 3, 4}, { 5, 8}, { 0,12}, { 2, 6},
{ 0, 1}, { 2, 3}, { 4, 6}, { 8,11}, { 7,12}, { 5, 9},
{ 0, 2}, { 3, 7}, {10,11}, { 1, 4}, { 6,12},
{ 7, 8}, {11,12}, { 4, 9}, { 6,10},
{ 3, 4}, { 5, 6}, { 8, 9}, {10,11}, { 1, 7},
{ 2, 6}, { 9,11}, { 1, 3}, { 4, 7}, { 8,10}, { 0, 5},
{ 2, 5}, { 6, 8}, { 9,10},
{ 1, 2}, { 3, 5}, { 7, 8}, { 4, 6},
{ 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 3, 4}, { 5, 6},
};
static const unsigned int network14[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13},
{ 5,10}, { 6, 9}, { 3,12}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network15[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network16[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11}, {13,15},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7}, {11,15},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14}, { 7,15},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network17[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {15,16},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {14,16},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {14,15}, {13,16},
{ 1, 5}, { 2, 6}, {12,15}, {11,16},
{ 1, 4}, { 3, 6}, {12,14}, {13,15}, { 7,16},
{ 2, 4}, { 3, 5}, {13,14}, {10,15},
{ 3, 4}, { 8,13}, { 9,14}, {11,15},
{ 8,12}, { 9,13}, {11,14}, { 6,15},
{ 9,12}, {10,13}, { 5,14}, { 7,15},
{10,12}, {11,13}, { 0, 9}, { 7,14},
{11,12}, { 0, 8}, { 1,10}, { 4,13},
{ 1, 9}, { 2,11}, { 3,12}, { 5,13},
{ 1, 8}, { 3,11}, { 2, 9}, { 6,13},
{ 2, 8}, { 3,10}, { 7,13}, { 6,11},
{ 3, 9}, { 5,10}, { 7,12},
{ 3, 8}, { 4, 9}, { 7,11},
{ 4, 8}, { 5, 9}, { 7,10},
{ 5, 8}, { 6, 9},
{ 6, 8}, { 7, 9},
{ 7, 8},
};
static const unsigned int network18[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17},
{ 0, 2}, { 1, 3}, { 6, 8}, { 9,11}, {10,12}, {15,17},
{ 1, 2}, { 6, 7}, { 5, 8}, {10,11}, {15,16}, {14,17},
{ 4, 7}, { 3, 8}, {13,16}, {12,17},
{ 4, 6}, { 5, 7}, {13,15}, {14,16}, { 8,17},
{ 5, 6}, { 2, 7}, {14,15}, {11,16},
{ 0, 5}, { 1, 6}, { 3, 7}, { 9,14}, {10,15}, {12,16},
{ 0, 4}, { 1, 5}, { 3, 6}, { 9,13}, {10,14}, {12,15}, { 7,16},
{ 1, 4}, { 2, 5}, {10,13}, {11,14}, { 0, 9}, { 6,15}, { 8,16},
{ 2, 4}, { 3, 5}, {11,13}, {12,14}, { 1,10}, { 7,15},
{ 3, 4}, {12,13}, { 1, 9}, { 2,11}, { 5,14}, { 8,15},
{ 3,12}, { 2, 9}, { 4,13}, { 7,14},
{ 3,11}, { 5,13}, { 8,14},
{ 3,10}, { 6,13},
{ 3, 9}, { 7,13}, { 5,10}, { 6,11},
{ 8,13}, { 4, 9}, { 7,12},
{ 5, 9}, { 8,12}, { 7,11},
{ 8,11}, { 6, 9}, { 7,10},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network19[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {12,13}, {14,15}, {17,18},
{ 0, 2}, { 1, 3}, { 6, 8}, {11,13}, {16,18},
{ 1, 2}, { 6, 7}, { 5, 8}, {11,12}, {10,13}, {16,17}, {15,18},
{ 4, 7}, { 3, 8}, { 9,12}, {14,17}, {13,18},
{ 4, 6}, { 5, 7}, { 9,11}, {10,12}, {14,16}, {15,17}, { 8,18},
{ 5, 6}, { 2, 7}, {10,11}, {15,16}, { 9,14}, {12,17},
{ 0, 5}, { 1, 6}, { 3, 7}, {10,15}, {11,16}, {13,17},
{ 0, 4}, { 1, 5}, { 3, 6}, {10,14}, {12,16}, { 7,17},
{ 1, 4}, { 2, 5}, {13,16}, {11,14}, {12,15}, { 0,10}, { 8,17},
{ 2, 4}, { 3, 5}, {13,15}, {12,14}, { 0, 9}, { 1,11}, { 6,16},
{ 3, 4}, {13,14}, { 1,10}, { 2,12}, { 5,15}, { 7,16},
{ 1, 9}, { 3,13}, { 2,10}, { 4,14}, { 8,16}, { 7,15},
{ 3,12}, { 2, 9}, { 5,14}, { 8,15},
{ 3,11}, { 6,14},
{ 3,10}, { 7,14}, { 6,11},
{ 3, 9}, { 8,14}, { 5,10}, { 7,12},
{ 4, 9}, { 8,13}, { 7,11},
{ 5, 9}, { 8,12}, { 7,10},
{ 8,11}, { 6, 9},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network20[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {15,16}, {18,19},
{ 2, 4}, { 7, 9}, {12,14}, {17,19},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {17,18}, {16,19},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {14,19},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {15,17}, {16,18}, { 9,19},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {16,17}, {10,15}, {13,18},
{ 1, 6}, { 2, 7}, { 4, 8}, {11,16}, {12,17}, {14,18}, { 0,10},
{ 1, 5}, { 3, 7}, {11,15}, {13,17}, { 8,18},
{ 4, 7}, { 2, 5}, { 3, 6}, {14,17}, {12,15}, {13,16}, { 1,11}, { 9,18},
{ 4, 6}, { 3, 5}, {14,16}, {13,15}, { 1,10}, { 2,12}, { 7,17},
{ 4, 5}, {14,15}, { 3,13}, { 2,10}, { 6,16}, { 8,17},
{ 4,14}, { 3,12}, { 5,15}, { 9,17}, { 8,16},
{ 4,13}, { 3,11}, { 6,15}, { 9,16},
{ 4,12}, { 3,10}, { 7,15},
{ 4,11}, { 8,15}, { 7,12},
{ 4,10}, { 9,15}, { 6,11}, { 8,13},
{ 5,10}, { 9,14}, { 8,12},
{ 6,10}, { 9,13}, { 8,11},
{ 9,12}, { 7,10},
{ 9,11}, { 8,10},
{ 9,10},
};
static const unsigned int network21[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {16,17}, {19,20},
{ 2, 4}, { 7, 9}, {12,14}, {15,17}, {18,20},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {15,16}, {18,19}, {17,20},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {16,19}, {14,20},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {17,19}, {16,18}, { 9,20},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {17,18}, {10,16}, {13,19},
{ 1, 6}, { 2, 7}, { 4, 8}, {10,15}, {11,17}, {12,18}, {14,19},
{ 1, 5}, { 3, 7}, {11,16}, {13,18}, { 8,19},
{ 4, 7}, { 2, 5}, { 3, 6}, {11,15}, {14,18}, {13,16}, { 9,19},
{ 4, 6}, { 3, 5}, {12,15}, {14,17}, { 0,11}, { 7,18},
{ 4, 5}, {14,16}, {13,15}, { 0,10}, { 1,12}, { 6,17}, { 8,18},
{14,15}, { 1,11}, { 2,13}, { 5,16}, { 9,18}, { 8,17},
{ 1,10}, { 3,14}, { 4,15}, { 6,16}, { 9,17},
{ 4,14}, { 3,13}, { 2,10}, { 7,16},
{ 4,13}, { 3,11}, { 8,16},
{ 4,12}, { 3,10}, { 9,16}, { 7,13}, { 8,14},
{ 4,11}, { 6,12}, { 9,15}, { 8,13},
{ 4,10}, { 5,11}, { 9,14},
{ 5,10}, { 6,11}, { 9,13},
{ 6,10}, { 8,11}, { 9,12},
{ 7,10}, { 9,11},
{ 8,10},
{ 9,10},
};
static const unsigned int network22[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21},
{ 2, 4}, { 5, 7}, { 8,10}, {13,15}, {16,18}, {19,21},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {13,14}, {12,15}, {16,17}, {19,20}, {18,21},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {16,19}, {17,20}, {15,21},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {11,13}, {12,14}, {18,20}, {17,19}, {10,21},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {12,13}, {18,19}, {11,17}, {14,20},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {11,16}, {12,18}, {13,19}, {15,20},
{ 1, 6}, { 3, 8}, {12,17}, {14,19}, { 0,11}, { 9,20},
{ 1, 5}, { 4, 8}, { 3, 6}, {12,16}, {15,19}, {14,17}, {10,20},
{ 2, 5}, { 4, 7}, {13,16}, {15,18}, { 1,12}, { 8,19},
{ 4, 6}, { 3, 5}, {15,17}, {14,16}, { 1,11}, { 2,13}, { 7,18}, { 9,19},
{ 4, 5}, {15,16}, { 3,14}, { 2,11}, { 6,17}, {10,19},
{ 4,15}, { 3,13}, { 5,16}, { 7,17}, {10,18},
{ 4,14}, { 3,12}, { 6,16}, { 9,17},
{ 4,13}, { 3,11}, { 7,16}, {10,17},
{ 4,12}, { 8,16}, { 7,13},
{ 4,11}, { 9,16}, { 6,12}, { 8,14},
{10,16}, { 5,11}, { 7,12}, { 9,15},
{ 6,11}, {10,15}, { 9,14},
{ 7,11}, {10,14}, { 9,12},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network23[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {12,13}, {15,16}, {18,19}, {21,22},
{ 2, 4}, { 5, 7}, { 8,10}, {11,13}, {14,16}, {17,19}, {20,22},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {11,12}, {14,15}, {13,16}, {17,18}, {20,21}, {19,22},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {12,15}, {17,20}, {18,21}, {16,22},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {13,15}, {12,14}, {19,21}, {18,20}, {11,17}, {10,22},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {13,14}, {19,20}, {12,18}, {15,21},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {13,19}, {12,17}, {14,20}, {16,21},
{ 1, 6}, { 3, 8}, {13,18}, {15,20}, { 0,12}, { 9,21},
{ 1, 5}, { 4, 8}, { 3, 6}, {13,17}, {16,20}, {15,18}, { 0,11}, {10,21},
{ 2, 5}, { 4, 7}, {14,17}, {16,19}, { 1,13}, { 8,20},
{ 4, 6}, { 3, 5}, {16,18}, {15,17}, { 1,12}, { 2,14}, { 7,19}, { 9,20},
{ 4, 5}, {16,17}, { 1,11}, { 3,15}, { 6,18}, {10,20},
{ 4,16}, { 3,14}, { 2,11}, { 5,17}, { 7,18}, {10,19},
{ 4,15}, { 3,12}, { 6,17}, { 9,18},
{ 4,14}, { 3,11}, { 7,17}, {10,18},
{ 4,13}, { 8,17},
{ 4,12}, { 9,17}, { 7,13}, { 8,14},
{ 4,11}, {10,17}, { 6,12}, { 9,15},
{ 5,11}, { 7,12}, {10,16}, { 9,14},
{ 6,11}, {10,15}, { 9,12},
{ 7,11}, {10,14},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network24[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {22,23},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {21,22}, {20,23},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,21}, {19,22}, {17,23},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {20,22}, {19,21}, {12,18}, {11,23},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {20,21}, {13,19}, {16,22}, { 0,12},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {14,20}, {13,18}, {15,21}, {17,22},
{ 2, 7}, { 4, 9}, {14,19}, {16,21}, { 1,13}, {10,22},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,18}, {17,21}, {16,19}, { 1,12}, {11,22},
{ 3, 6}, { 5, 8}, {15,18}, {17,20}, { 2,14}, { 9,21},
{ 5, 7}, { 4, 6}, {17,19}, {16,18}, { 2,13}, { 3,15}, { 8,20}, {10,21},
{ 5, 6}, {17,18}, { 2,12}, { 4,16}, { 7,19}, {11,21},
{ 5,17}, { 4,15}, { 3,12}, { 6,18}, { 8,19}, {11,20},
{ 5,16}, { 4,13}, { 7,18}, {10,19},
{ 5,15}, { 4,12}, { 8,18}, {11,19},
{ 5,14}, { 9,18},
{ 5,13}, {10,18}, { 8,14}, { 9,15},
{ 5,12}, {11,18}, { 7,13}, {10,16},
{ 6,12}, { 8,13}, {11,17}, {10,15},
{ 7,12}, {11,16}, {10,13},
{ 8,12}, {11,15},
{ 9,12}, {11,14},
{11,13}, {10,12},
{11,12},
};
static const unsigned int network25[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {21,22}, {23,24},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23}, {22,24},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {22,23}, {20,24},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,22}, {19,23}, {17,24},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {18,21}, {20,23}, {11,24},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {19,21}, {20,22}, {16,23},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {20,21}, {12,19}, {15,22}, {17,23},
{ 2, 7}, { 4, 9}, {12,18}, {13,20}, {14,21}, {16,22}, {10,23},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,20}, {13,18}, {17,22}, {11,23},
{ 3, 6}, { 5, 8}, {14,19}, {16,20}, {17,21}, { 0,13}, { 9,22},
{ 5, 7}, { 4, 6}, {14,18}, {15,19}, {17,20}, { 0,12}, { 8,21}, {10,22},
{ 5, 6}, {15,18}, {17,19}, { 1,14}, { 7,20}, {11,22},
{16,18}, { 2,15}, { 1,12}, { 6,19}, { 8,20}, {11,21},
{17,18}, { 2,14}, { 3,16}, { 7,19}, {10,20},
{ 2,13}, { 4,17}, { 5,18}, { 8,19}, {11,20},
{ 2,12}, { 5,17}, { 4,16}, { 3,13}, { 9,19},
{ 5,16}, { 3,12}, { 4,14}, {10,19},
{ 5,15}, { 4,12}, {11,19}, { 9,16}, {10,17},
{ 5,14}, { 8,15}, {11,18}, {10,16},
{ 5,13}, { 7,14}, {11,17},
{ 5,12}, { 6,13}, { 8,14}, {11,16},
{ 6,12}, { 8,13}, {10,14}, {11,15},
{ 7,12}, { 9,13}, {11,14},
{ 8,12}, {11,13},
{ 9,12},
{10,12},
{11,12},
};
static const unsigned int network26[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21}, {22,23}, {24,25},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {19,21}, {22,24}, {23,25},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {16,17}, {15,18}, {19,20}, {23,24}, {21,25},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,16}, {14,17}, {19,23}, {20,24}, {18,25},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {15,17}, {14,16}, {19,22}, {21,24}, {12,25},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {15,16}, {20,22}, {21,23}, {17,24},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {21,22}, {13,20}, {16,23}, {18,24},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {13,19}, {14,21}, {15,22}, {17,23}, {11,24},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {14,19}, {18,23}, { 0,13}, {12,24},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {17,21}, {18,22}, { 1,14}, {10,23},
{ 2, 6}, { 3, 7}, { 5, 8}, {15,19}, {16,20}, {18,21}, { 1,13}, { 9,22}, {12,23},
{ 3, 6}, { 5, 7}, {16,19}, {18,20}, { 2,15}, { 8,21}, {10,22},
{ 4, 6}, {17,19}, { 2,14}, { 3,16}, { 7,20}, {11,22},
{ 5, 6}, {18,19}, { 2,13}, { 4,17}, { 8,20}, {12,22}, {11,21},
{ 5,18}, { 4,16}, { 3,13}, { 6,19}, {10,20}, {12,21},
{ 5,17}, { 4,14}, { 7,19}, {12,20},
{ 5,16}, { 4,13}, { 8,19},
{ 5,15}, { 9,19},
{ 5,14}, {10,19}, { 8,15}, { 9,16},
{ 5,13}, {11,19}, { 7,14}, {10,17},
{12,19}, { 6,13}, { 8,14}, {10,16}, {11,18},
{ 7,13}, {12,18}, {11,16}, {10,14},
{ 8,13}, {12,17}, {11,15},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network27[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {16,17}, {18,19}, {21,22}, {23,24}, {25,26},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {17,19}, {20,22}, {23,25}, {24,26},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {17,18}, {15,19}, {20,21}, {24,25}, {22,26},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,17}, {14,18}, {20,24}, {21,25}, {19,26},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {13,16}, {15,18}, {20,23}, {22,25}, {12,26},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {14,16}, {15,17}, {21,23}, {22,24}, {13,20}, {18,25},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {15,16}, {22,23}, {14,21}, {17,24}, {19,25},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {15,22}, {14,20}, {16,23}, {19,24}, {11,25},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {17,23}, { 0,14}, {12,25},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {18,23}, {17,21}, { 0,13}, {10,24},
{ 2, 6}, { 3, 7}, { 5, 8}, {19,23}, {16,20}, {18,22}, { 1,15}, {12,24},
{ 3, 6}, { 5, 7}, {17,20}, {19,22}, { 2,16}, { 1,13}, { 9,23},
{ 4, 6}, {18,20}, {19,21}, { 2,15}, { 3,17}, { 8,22}, {10,23},
{ 5, 6}, {19,20}, { 2,14}, { 4,18}, { 7,21}, {11,23},
{ 2,13}, { 5,19}, { 4,17}, { 3,14}, { 6,20}, { 8,21}, {12,23}, {11,22},
{ 5,18}, { 3,13}, { 4,15}, { 7,20}, {10,21}, {12,22},
{ 5,17}, { 4,13}, { 8,20}, {12,21},
{ 5,16}, { 9,20},
{ 5,15}, {10,20}, { 9,16},
{ 5,14}, {11,20}, { 8,15}, {10,17},
{ 5,13}, {12,20}, { 7,14}, {10,16}, {11,18},
{ 6,13}, { 8,14}, {12,19}, {11,16},
{ 7,13}, {12,18}, {10,14}, {11,15},
{ 8,13}, {12,17},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network28[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {22,23}, {24,25}, {26,27},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {24,26}, {25,27},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {21,22}, {25,26}, {23,27},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {21,25}, {22,26}, {20,27},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {21,24}, {23,26}, {13,27},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {22,24}, {23,25}, {14,21}, {19,26},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {23,24}, {15,22}, {18,25}, {20,26}, { 0,14},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,23}, {15,21}, {17,24}, {20,25}, {12,26},
{ 2, 8}, { 4,10}, {16,22}, {18,24}, { 1,15}, {11,25}, {13,26},
{ 2, 7}, { 5,10}, { 4, 8}, {16,21}, {19,24}, {18,22}, { 1,14}, {13,25},
{ 6,10}, { 3, 7}, { 5, 9}, {20,24}, {17,21}, {19,23}, { 2,16},
{ 4, 7}, { 6, 9}, {18,21}, {20,23}, { 2,15}, { 3,17}, {10,24},
{ 5, 7}, { 6, 8}, {19,21}, {20,22}, { 2,14}, { 4,18}, { 9,23}, {11,24},
{ 6, 7}, {20,21}, { 4,17}, { 5,19}, { 3,14}, { 8,22}, {12,24},
{ 6,20}, { 5,17}, { 4,15}, { 7,21}, { 9,22}, {13,24}, {12,23},
{ 6,19}, { 4,14}, { 5,16}, { 8,21}, {11,22}, {13,23},
{ 6,18}, { 5,14}, { 9,21}, {13,22},
{ 6,17}, {10,21},
{ 6,16}, {11,21}, {10,17},
{ 6,15}, {12,21}, { 9,16}, {11,18},
{ 6,14}, {13,21}, { 8,15}, {11,17}, {12,19},
{ 7,14}, { 9,15}, {13,20}, {12,17},
{ 8,14}, {13,19}, {11,15}, {12,16},
{ 9,14}, {13,18},
{13,17}, {10,14},
{11,14}, {13,16},
{12,14}, {13,15},
{13,14},
};
static const unsigned int network29[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {22,24}, {25,27}, {26,28},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {22,23}, {26,27}, {21,25}, {24,28},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {22,26}, {23,27}, {20,28},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {22,25}, {24,27}, {13,28},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {23,25}, {24,26}, {14,22}, {19,27},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {24,25}, {14,21}, {15,23}, {18,26}, {20,27},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,24}, {15,21}, {17,25}, {20,26}, {12,27},
{ 2, 8}, { 4,10}, {16,23}, {18,25}, { 0,15}, {11,26}, {13,27},
{ 2, 7}, { 5,10}, { 4, 8}, {16,22}, {19,25}, { 0,14}, {13,26},
{ 6,10}, { 3, 7}, { 5, 9}, {16,21}, {20,25}, {18,22}, {19,23},
{ 4, 7}, { 6, 9}, {17,21}, {20,24}, { 1,16}, {10,25},
{ 5, 7}, { 6, 8}, {18,21}, {20,23}, { 2,17}, { 1,14}, { 9,24}, {11,25},
{ 6, 7}, {19,21}, {20,22}, { 2,16}, { 3,18}, { 8,23}, {12,25},
{20,21}, { 2,15}, { 4,19}, { 7,22}, { 9,23}, {13,25}, {12,24},
{ 2,14}, { 4,18}, { 5,20}, { 6,21}, { 8,22}, {11,23}, {13,24},
{ 6,20}, { 5,18}, { 3,14}, { 4,15}, { 9,22}, {13,23},
{ 6,19}, { 4,14}, { 5,16}, {10,22},
{ 6,18}, { 5,14}, {11,22},
{ 6,17}, {12,22}, {10,18}, {11,19},
{ 6,16}, {13,22}, { 9,17}, {11,18}, {12,20},
{ 6,15}, { 8,16}, {13,21}, {12,18},
{ 6,14}, { 7,15}, { 9,16}, {13,20},
{ 7,14}, { 9,15}, {13,19}, {12,16},
{ 8,14}, {13,18}, {11,15},
{ 9,14}, {13,17},
{10,14}, {13,16},
{11,14}, {13,15},
{12,14},
{13,14},
};
static const unsigned int network30[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {18,20}, {19,21}, {22,24}, {23,25}, {26,28}, {27,29},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {15,16}, {19,20}, {17,21}, {23,24}, {27,28}, {22,26}, {25,29},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {15,19}, {16,20}, {23,27}, {24,28}, {21,29},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {15,18}, {17,20}, {23,26}, {25,28}, {14,29},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {16,18}, {17,19}, {24,26}, {25,27}, {15,23}, {20,28},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {17,18}, {25,26}, {15,22}, {16,24}, {19,27}, {21,28},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {17,25}, {16,22}, {18,26}, {21,27}, { 0,15}, {13,28},
{ 2, 9}, { 4,11}, {17,24}, {19,26}, { 1,16}, {12,27}, {14,28},
{ 2, 8}, { 5,11}, {17,23}, {20,26}, { 1,15}, {14,27},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {17,22}, {21,26}, {19,23}, {20,24},
{ 3, 7}, { 6,10}, {18,22}, {21,25}, { 2,17}, {11,26},
{ 4, 7}, { 6, 9}, {19,22}, {21,24}, { 2,16}, { 3,18}, {10,25}, {12,26},
{ 5, 7}, { 6, 8}, {20,22}, {21,23}, { 2,15}, { 4,19}, { 9,24}, {13,26},
{ 6, 7}, {21,22}, { 4,18}, { 5,20}, { 3,15}, { 8,23}, {10,24}, {14,26},
{ 6,21}, { 5,18}, { 4,16}, { 7,22}, {10,23}, {13,24}, {14,25},
{ 6,20}, { 4,15}, { 5,17}, { 8,22}, {12,23}, {14,24},
{ 6,19}, { 5,15}, { 9,22}, {14,23},
{ 6,18}, {10,22},
{ 6,17}, {11,22}, {10,18},
{ 6,16}, {12,22}, { 9,17}, {11,19},
{ 6,15}, {13,22}, { 8,16}, {10,17}, {12,20},
{14,22}, { 7,15}, {10,16}, {12,19}, {13,21},
{ 8,15}, {14,21}, {13,19}, {12,16},
{ 9,15}, {14,20}, {13,17},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network31[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28}, {29,30},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {16,18}, {19,21}, {20,22}, {23,25}, {24,26}, {27,29}, {28,30},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {16,17}, {20,21}, {15,19}, {18,22}, {24,25}, {28,29}, {23,27}, {26,30},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {16,20}, {17,21}, {24,28}, {25,29}, {15,23}, {22,30},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {16,19}, {18,21}, {24,27}, {26,29}, {14,30},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {17,19}, {18,20}, {25,27}, {26,28}, {16,24}, {21,29},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {18,19}, {26,27}, {16,23}, {17,25}, {20,28}, {22,29},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {18,26}, {17,23}, {19,27}, {22,28}, { 0,16}, {13,29},
{ 2, 9}, { 4,11}, {18,25}, {20,27}, { 0,15}, { 1,17}, {12,28}, {14,29},
{ 2, 8}, { 5,11}, {18,24}, {21,27}, { 1,15}, {14,28},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {18,23}, {22,27}, {20,24}, {21,25},
{ 3, 7}, { 6,10}, {19,23}, {22,26}, { 2,18}, {11,27},
{ 4, 7}, { 6, 9}, {20,23}, {22,25}, { 2,17}, { 3,19}, {10,26}, {12,27},
{ 5, 7}, { 6, 8}, {21,23}, {22,24}, { 2,16}, { 4,20}, { 9,25}, {13,27},
{ 6, 7}, {22,23}, { 2,15}, { 4,19}, { 5,21}, { 8,24}, {10,25}, {14,27},
{ 6,22}, { 5,19}, { 3,15}, { 4,16}, { 7,23}, {10,24}, {13,25}, {14,26},
{ 6,21}, { 4,15}, { 5,17}, { 8,23}, {12,24}, {14,25},
{ 6,20}, { 5,15}, { 9,23}, {14,24},
{ 6,19}, {10,23},
{ 6,18}, {11,23},
{ 6,17}, {12,23}, {10,18}, {11,19},
{ 6,16}, {13,23}, { 9,17}, {12,20},
{ 6,15}, {14,23}, { 8,16}, {10,17}, {12,19}, {13,21},
{ 7,15}, {10,16}, {14,22}, {13,19},
{ 8,15}, {14,21}, {12,16}, {13,17},
{ 9,15}, {14,20},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network32[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29}, {30,31},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {12,14}, {13,15}, {16,18}, {17,19}, {20,22}, {21,23}, {24,26}, {25,27}, {28,30}, {29,31},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {13,14}, { 8,12}, {11,15}, {17,18}, {21,22}, {16,20}, {19,23}, {25,26}, {29,30}, {24,28}, {27,31},
{ 1, 5}, { 2, 6}, { 9,13}, {10,14}, { 0, 8}, { 7,15}, {17,21}, {18,22}, {25,29}, {26,30}, {16,24}, {23,31},
{ 1, 4}, { 3, 6}, { 9,12}, {11,14}, {17,20}, {19,22}, {25,28}, {27,30}, { 0,16}, {15,31},
{ 2, 4}, { 3, 5}, {10,12}, {11,13}, { 1, 9}, { 6,14}, {18,20}, {19,21}, {26,28}, {27,29}, {17,25}, {22,30},
{ 3, 4}, {11,12}, { 1, 8}, { 2,10}, { 5,13}, { 7,14}, {19,20}, {27,28}, {17,24}, {18,26}, {21,29}, {23,30},
{ 3,11}, { 2, 8}, { 4,12}, { 7,13}, {19,27}, {18,24}, {20,28}, {23,29}, { 1,17}, {14,30},
{ 3,10}, { 5,12}, {19,26}, {21,28}, { 1,16}, { 2,18}, {13,29}, {15,30},
{ 3, 9}, { 6,12}, {19,25}, {22,28}, { 2,16}, {15,29},
{ 3, 8}, { 7,12}, { 5, 9}, { 6,10}, {19,24}, {23,28}, {21,25}, {22,26},
{ 4, 8}, { 7,11}, {20,24}, {23,27}, { 3,19}, {12,28},
{ 5, 8}, { 7,10}, {21,24}, {23,26}, { 3,18}, { 4,20}, {11,27}, {13,28},
{ 6, 8}, { 7, 9}, {22,24}, {23,25}, { 3,17}, { 5,21}, {10,26}, {14,28},
{ 7, 8}, {23,24}, { 3,16}, { 5,20}, { 6,22}, { 9,25}, {11,26}, {15,28},
{ 7,23}, { 6,20}, { 4,16}, { 5,17}, { 8,24}, {11,25}, {14,26}, {15,27},
{ 7,22}, { 5,16}, { 6,18}, { 9,24}, {13,25}, {15,26},
{ 7,21}, { 6,16}, {10,24}, {15,25},
{ 7,20}, {11,24},
{ 7,19}, {12,24},
{ 7,18}, {13,24}, {11,19}, {12,20},
{ 7,17}, {14,24}, {10,18}, {13,21},
{ 7,16}, {15,24}, { 9,17}, {11,18}, {13,20}, {14,22},
{ 8,16}, {11,17}, {15,23}, {14,20},
{ 9,16}, {15,22}, {13,17}, {14,18},
{10,16}, {15,21},
{11,16}, {15,20},
{12,16}, {15,19},
{13,16}, {15,18},
{14,16}, {15,17},
{15,16},
};
typedef struct {
const unsigned int comparators;
const unsigned int (*pNetwork)[2];
} Network;
#define elemof(ary) (sizeof(ary)/sizeof(ary[0]))
#define NETWORK(n) {elemof(network##n), network##n}
static const Network networks[] = {
{0, NULL},
{0, NULL},
NETWORK(02),
NETWORK(03),
NETWORK(04),
NETWORK(05),
NETWORK(06),
NETWORK(07),
NETWORK(08),
NETWORK(09),
NETWORK(10),
NETWORK(11),
NETWORK(12),
NETWORK(13),
NETWORK(14),
NETWORK(15),
NETWORK(16),
NETWORK(17),
NETWORK(18),
NETWORK(19),
NETWORK(20),
NETWORK(21),
NETWORK(22),
NETWORK(23),
NETWORK(24),
NETWORK(25),
NETWORK(26),
NETWORK(27),
NETWORK(28),
NETWORK(29),
NETWORK(30),
NETWORK(31),
NETWORK(32),
};
#undef NETWORK
static const size_t cutoff = elemof(networks);
template
inline void networkSort(Elem *p, size_t n) {
const unsigned int (* pNetwork)[2], (* pEnd)[2];
Elem *p0, *p1;
assert(n < elemof(networks));
pNetwork = networks[n].pNetwork;
pEnd = pNetwork + networks[n].comparators;
for(; pNetwork < pEnd; pNetwork++) {
p0 = p + (*pNetwork)[0];
p1 = p + (*pNetwork)[1];
if(*p1 < *p0) swap(p0, p1);
}
}
[/cc]
号称世界上最难的逻辑题
已知:
1.神无所不知只说真话,鬼无所不知只说假话,人有所不知胡乱说话,除此之外三者没有任何区别。他们一定回答且只能回答任何有确定答案的是非题。
2.“Da”和“Ja”一个永远代表“是”另一个永远代表“否”,但你完全不知道二者分别代表哪个。
问题Z:你面前站着神、鬼、人各一,你不知道三者分别是谁,你必须通过提问正确区分出三者。你每次只能对其中一个提问,一共只能问三次,但你每次提问得到的回答只能是“Da”或“Ja”。
如果你觉得Z太难,这里有一个简化版Z’:跟Z类似,但得到的答案只能是“是”或“否”。
如果你还是觉得太难,还有一个更简单的问题Y:你面前有两条路,一条通向天堂,一条通向地狱。路口站着神、鬼各一,你不知道二者分别是谁。你现在只能对其中一个提出一个是非题,判断出哪条路通向天堂。但你提问得到的回答只会是“Da”或“Ja”。
如果你觉得Y也太难,也可以简化为Y’:跟Y类似,但得到的答案只会是“是”或“否”。
附加条件:
如果你解决了Z或Z’,那么请加一个条件:你对其中一个问的问题中不允许同时提及另外两个。
如果你解决了Y或Y’,那么请加一个条件:你对其中一个问的问题中不允许提及另外一个。
问题Y还可以有如下变体Y”:路口只站着一个家伙,你只知道他要么是神要么是鬼。你现在只能向他问一个是非题,判断出哪条路通向天堂。其他不变。
一点提示:
对A提问:『将鬼、人、神分别编号为1,2,3,那么请问B的编号大于C么?』
对A提问:『如果我问你『B是乱说话的人么?』,你会回答什么?』
对任何一个提问:请问『……』这个问题的答案是Da么?
二元关系学习总结
preorder(预序): reflexive, transitive
partial order(偏序,对应图论的有向无环图): preorder + anti-symmetric
total preorder(完全预序): preorder + total
equivalence(等价): preorder + symmetric
complete(全互连,对应图论的完全连通图): total preorder + symmetric or equivalence + total
equality(相等): equivalence + anti-symmetric or partial order + symmetic
total order(全序): partial order + total or total preorder + anti-symmetric
(total order, AKA linear order, simple order, or (non-strict) ordering)
注意,上述关系中的后三个关系所用到的某些属性已经不是独立的了,例如相等关系用自反性、对称性、反对称性就可以导出传递性(因为对称性和反对称性限制了关系只能发生在每个元素自身上,自反性则保证了每个元素自身都满足这个关系。结果没有可能发生传递,因此传递性自然被满足。)
上面的提到的各种关系R所用到的各种属性:
reflexive(自反性): for all x in X it holds that xRx
transitive(传递性): for all x, y and z in X it holds that if xRy and yRz then xRz.
symmetric(对称性): for all x and y in X it holds that if xRy then yRx
anti-symmetric(反对称性): for all x and y in X it holds that if xRy and yRx then x = y
total(完全性): for all x and y in X it holds that xRy or yRx (or both)
二元关系的其它一些常见属性:
irreflexive(非自反性): for all x in X it holds that not xRx
coreflexive(伴自反性): for all x and y in X it holds that if xRy then x = y
asymmetric(非对称性): for all x and y in X it holds that if xRy then not yRx
[cc lang=”cpp”]
PR
/|\
/ | \
/ | \
/ | \
PA TP EV
|\ /\ /|
| \/ \/ |
| /\ /\ |
|/ \/ \|
TO EQ CP
[/cc]
PR: preorder
PA: partial order
TP: total preorder
EV: equivalence
TO: total order
EQ: equality
CP: complete connection
/: anti-symmetric
|: total
\: symmetric
一个重要的未讨论过的关系:
well order(良序): total order + well-founded
well-founded(良基关系):every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s≠m of S, the pair (s,m) is not in R.
If a set is totally ordered, then the following are equivalent:
1. The set is well-ordered. That is, every nonempty subset has a least element.
2. Transfinite induction works for the entire ordered set.
3. Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice).
其它关系:
* Dependency relation, a symmetric, reflexive relation.
* Independency relation, a symmetric, irreflexive relation.
这两种关系是互补的。
图灵机vs数学家——图灵机计算能力的分析
(这是我2009年5月在繁星客栈上发表的,现稍加修改放在这里)
这里我尝试回答三个问题
0.是否存在数学家可以做出判定的问题,不存在判定该问题的图灵机?
1.是否存在这样的通用判定图灵机,输入任何数学家可以判定的问题,该图灵机都能在有限步骤之内输出其判定结果,而不输出任何错误的判定结果?
2.是否存在这样的自动判定图灵机,自动尝试判定所有可能的判定问题,而对于其中任何一个数学家可以判定的问题,该图灵机都可以在有限步骤之内输出其判定结果,而不输出任何错误的判定结果?
现在我们对数学家做一个假定:只有能够完全形式化的有限判定过程,才会被数学家承认。
这个假定是合理的,虽然天才的数学家可以用直觉、灵感、做梦、神启等等各种惊人的手段获得一个问题判定结果,但只有能够被彻底形式化的有限判定过程才会被认为是可靠的判定过程。换言之,任何一个能够被数学家认可的判定过程,绝对不能包含任何直觉成分。
上述假定蕴含这样一个结果:
能被数学家承认的任何判定,其步骤数目必然有限。
能被数学家判定的任何问题,其符号刻画必然有限。
有限符号可刻画的问题的全集显然是递归可枚举集,因为它是所有有限长字符串集合的子集,因此可以用自然数i进行编号,记为Pi。
同理,刻画任何有效判定过程的符号串长度必然有限,因此显然是递归可枚举集,也可以用自然数j进行编号,记为Dj。
任何形式系统的推理规则,至多属于乔姆斯基无限制文法的子集,因此推理规则所生成的语言必然是递归可枚举语言的子集,而递归可枚举语言是图灵机可接受(但未必可判定)语言。所有形式系统的推理规则,都可以用自然数k进行编号,记为Lk。
判定【Dj是否为Lk的问题Pi的有效判定过程】,可以用一个通用验证图灵机V(Lk,Pi,Dj)进行判定,而且这是个可判定过程。因为Lk中任何一个判定过程中的任何一个步骤否有效,可以直接套用Lk的推理规则进行判定,而由于整个判定过程的步骤必然有限,因此整个判定过程Dj的有效性必然是可以被图灵机V判定的。
现在我们来构造一个图灵机H(Lk,Pi),对于给定的形式系统Lk以及Lk的问题Pi,如果Lk中存在对Pi的有效判定过程Dj,那么图灵机H就输出Pi在Lk内的判定结果。但如果Lk中不存在对Pi的有效判定,H永不停机。
为了构造H,我们先考虑一个不可行的构造,然后将其改造为可行的构造:
构造无穷多图灵机Hj(Lk,Pi),其定义为V(Lk,Pi,Dj)。显然,如果存在某个j,Dj是Pi在Lk下的有效判定,那么Hj必然在有限步骤内停机。
如果将所有的Hj同时启动,那么只要问题Pi在Lk下可判定,那么至少有一个Hj会在有限时间内输出判定,除非问题Pj在Lk下不可判定。
但是上述机构造需要同时运行无数个图灵机,是不可接受的。不过很容易将上述改造为可接受的构造:
构造H(Lk,Pi),H包含一个循环,在第j次循环中,H先枚举出图灵机Hj的仿真程序,然后将已经枚举出的图灵机H0-Hj的仿真程序分别单步执行一步。显然,H的任何一次循环都必然在有限步骤内结束,只不过越往后循环周期越长。这样,只要Pi在Lk内可判定,那么必然存在某个Hj在运行m个步骤后停机给出判定结果,那么H(Lk,Pi)就必然在第j+m个循环之内停机。反之,如果Pi在Lk内不可判定,那么H永远也不停机。
于是,H就是符合前述要求的图灵机。
现在,我们要利用H(Lk,Pi,Dk)来构造一个永不停机的图灵机X,X不接受任何输入,但X对于任何一个形式系统Lk中任何一个可判定问题Pi,都可以在有限时间内输出其判定结果(连同Lk和Pi的编号一起输出),而对于任何一个不可判定的问题,X都永远不给出对该问题的任何输出。
类似于构造H的过程,我们先考虑一个不可行的构造,然后改造为可行的构造:
二元组(Lk,Pi)显然是一个递归可枚举集,因此可以用自然数n进行编号:n=f(Lk,Pi),(Lk,Pi)=g(n),f和g互为反函数。
构造无穷多图灵机Xn,其定义为:如果H(g(n))停机输出判定结果d,Xn就输出(n,d)。显然,只要Pi在Lk中可判定,Xn就必然在有限步骤内停机并输出(n,d),反之Xn永不停机。
如果将所有的Xn同时启动,那么任何Lk中的任何可判定问题Pi,都必然在有限步骤内被某个Xn输出,输出内容为(n,d),其中n=f(Lk,Pi)。
上述构造当然也是不可接受的,我们仿照改造H的方法改造X
构造图灵机X,X包含一个循环,在第n次循环中,X先枚举出图灵机Xn的仿真程序,然后将已经枚举出的图灵机X0-Xn的仿真程序分别单步执行一步。显然,X的任何一次循环都必然在有限步骤内结束,只不过越往后循环周期越长。这样,对于任何Lk中的任何Pi,只要Pi在Lk中是可判定的且判定结果为d,那么Xn(n=f(Lk,Pi))必然在某个有限步骤s处停机并输(n,d),而Xn的第s步必然在X的第n+s个循环中被执行到,X必然在n+s个循环之内,输出(n,d)。对于任何形式系统中的任何不可判定的问题,X永远都不会输出判定结果。
于是,X就是符合前述要求的图灵机。
现在澄清几件事情:
1.H和X都不会对任何形式系统中的任何不可判定问题给出判定。
2.对于任何Lk中的任何【Pi】,无论【Pi】在Lk中是否可判定,都存在整数i’,使得【Pi’】==【Pi在Lk中可判定】,因此【Pi在Lk中可判定】这个问题迟早会被X枚举出来并尝试对之进行判定。只要【Pi在Lk中可判定】在某个形式系统Lk’中可判定,那么【Pi在Lk中可判定】的判定结果必然会在有限步骤内被X输出。
3.X在枚举Xn的过程中,许多Xn是根本不会停机的,而每次循环中X都必须单步执行所有尚未停机的Xn,因此X的效率会越来越低。但正如我们前面所讨论的,只要一个问题可以判定,X必然会在有限步骤内输出这个问题的判定,X的能力不会随着效率越来越低而变弱。如果实在觉得这种垃圾越来越多的系统很不舒服,那么还存在这样一个优化:每当某个Xn停机输出了某个问题A的判定结果,就检查A的内容是不是在断言另一个问题B不可判定,如果A有效断言出B不可判定,那么就将正在尝试判定B的图灵机从循环中删除。甚至还可以对B做个标记,在枚举新问题的时候,凡是将问题B作为子问题的问题,都将被直接跳过。不过这些优化其实没什么意义,我们的目的仅仅是讨论图灵机的计算能力,并不关心性能。
——————————————————————————————
现在说一点题外话,数学上明明允许图灵机不可判定的问题存在,也允许超越图灵机的计算模型存在,而我们仅仅对数学家做了一个简单的限制,数学家的计算能力就被限制成不超越图灵机了呢?
这个问题很简单。我们所说的形式系统当然都是有限刻画的。数学家可以谈论某些必须由无限符号才能刻画的数学系统的存在性,甚至谈论这些系统的某些能力和限制,但完全无法使用这些系统进行推理。我们之所以可以谈论这些系统的某些能力和限制,是因为精确分析这些东西仅仅需要有限符号。于是,图灵机也一样可以给出关于这些系统的某些有限符号就可以刻画的属性的判定结果。
事实上,即便是我们熟悉的实数集,其中属性能够被有限符号所精确刻画的实数(也包括π、e、γ等)也只是实数集的一个可数子集。
除非数学家可以分辨出连续统那么多不同的符号甚至更多,以至于整个实数轴的每一个实数对于数学家来说一目了然,那么数学家也就具备了Hyper Computing的能力,我在文章开头对数学家所做的假设也就不再成立了。但这种情况下,数学家所能够提出的机械计算模型肯定要比图灵机更强。这种数学家的本事简直赶上上帝了,我们有能力回答的一切数学问题,对于这种超级数学家来说都可以一眼看出答案。
暴力冲突——草稿
付诸实施的暴力往往意味着至少一方在赌博。
人通常不会对自己完全清楚的决无胜算的对手进行暴力反抗。比方说遇到山崩地裂,除了脑子进水的,没人会去对抗。
一般来说只有在双方都认为实施暴力有利于自己的情况下,才会发生暴力冲突。
此处要澄清一个误解:实力明显弱的一方有时明知会失败却也要暴力对抗强者,但这并不是反例。因为强者很可能并不完全了解弱者的实力,虽然占绝对优势,但如果强者知道弱者会尽力抵抗,仍然会对策略进行调整,从而导致对弱者有利的最终结果。如果双方都从一开始就知道双方的实力对比,而且双方都知道对方了解自己,弱者却仍然要暴力对抗强者,就说明弱者对暴力本身的有强烈偏好,或者对最大程度损害对手利益有强烈偏好,比方说那些电影里经常出现的为荣誉而战的战斗狂。这种情况下对于这种战斗狂来说实施暴力符合自己的偏好(有利),即便根本得不到其他的回报。
在上述意义上,当利益冲突的双方没有其它便宜的渠道获得对方实力信息,而又都认为暴力冲突有利于己方,就很可能实施暴力对抗。换言之,暴力对抗提供了一条了解对方实力信息的虽然血腥但却非常直接的途径。
当然,由于存在许多不可控因素,即便是实力上占优势的一方也未必一定能够在冲突中取得胜利,因此冲突往往带有赌博性质。弱势一方即便知道自己弱势,但又认为自己不是完全没有希望获胜,失败或者投降的结果对自己的偏好来说相差不多,那么弱势一方就很可能会暴力对抗强者。
————————————————————————
社会规则能够取代直接付诸实施的暴力产生效果仅仅是因为所有人都知道存在一个强大的未付诸实施的暴力(或者叫施暴的能力)做规则的保障。核威慑不但没有让世界变成核辐射地狱,反而带来了长时间的相对和平,这本身也是因为各参与方都非常清楚地知道别人手中握有巨大的施暴能力。当然这种核威慑下的和平到底能有多可靠就不是那么容易判断了,取决于许多细节因素。
有人用公司总裁作为例子来说明总裁权力的来源是股东的授权而并非来源于暴力。但如果没有背后的国家机器的暴力保障,总裁和股东手里的权力还存在么?总裁当然不需要直接施暴来执行自己的决策,总裁握有施暴的能力。只要总裁的行为是受法律保护的行为,那么在迫不得已必须通过暴力解决问题的时候,法律暴力就会站在总裁一边。正因为这种威慑,所以总裁通常根本不必真的施暴就可以迫使员工执行自己的决策。同样,只要法律不是专门为总裁服务的,那么如果员工的行为是受法律保护的,员工在自身行为合法的条件下也具有这种暴力威慑,于是总裁就不敢随便以非法的手段处置员工。
不要说人类,就连动物都是如此,握有施暴的能力,并且让对手知道自己有这种能力,那么通常就用不着真正施暴。一头狮子和一只鬣狗都要到小水洼里喝水,难道狮子还真得把鬣狗杀了才能安心喝水么?暴力最终付诸实施是因为双方在施暴之前都认为施暴所导致的后果更符合自己的意愿,有时这是因为弱势一方很不了解敌我实力对比,有时这是因为弱势一方认为投降比战败的结果更差。