08/10/13 21:07:02
Birkhoffの表現定理より有限集合上の位相は擬順序で表現できるから、
n点集合上の有向グラフを2^(n(n-1))個生成して擬順序として一致するものを数え上げる、
という方針で行ったらC++120行のプログラムで7点集合上の位相を数え上げできたよ。
なんでそんなに短くて済むかというと、擬順序はWarshall-Floydっぽい方法で
インクリメンタルに求めることが出来て、グラフの探索をまったくやらなくていいから。
計算時間の方は5年前のPowerBookで8分。T0限定だと200秒(結果は6129859通り)。
257:１３２人目の素数さん
08/10/14 07:59:27
すげえじゃん
やるじゃん
258:１３２人目の素数さん
08/10/14 14:23:22
時間の無駄だろ
259:１３２人目の素数さん
08/10/14 16:25:40
>>256
プログラム書き込みｷｳﾞｫﾝﾇ
260:１３２人目の素数さん
08/10/14 21:59:04
一般項って研究されてないのかな？
261:256
08/10/16 00:57:27
#include <algorithm>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <set>
/* #define SKIP_T0 */
#define N_VERT 7
typedef unsigned int vertex_t;
typedef unsigned char row_t;
struct AdjacencyMatrix {
row_t row[N_VERT]; // 辺(u,v)が存在するときrow[u]のvビット目を1とする
bool test(vertex_t u, vertex_t v) const
{ return row[u] & (1U<<v); }
void clear()
{ std::fill(row, row + N_VERT, 0); }
};
// 平衡木を使うためAdjacencyMatrixに順序を入れる
struct AdjacencyCompare : std::binary_function<AdjacencyMatrix, AdjacencyMatrix, bool> {
bool operator()(const AdjacencyMatrix &lhs, const AdjacencyMatrix &rhs)
{ return std::memcmp(lhs.row, rhs.row, N_VERT * sizeof(row_t)) < 0; }
};
// 既知の擬順序はSTLの平衡木で管理する(本当はハッシュテーブルの方がよい)
typedef std::set<AdjacencyMatrix, AdjacencyCompare> OrderDictionary;
262:256
08/10/16 00:59:32
// 2^(n(n-1))通りの有向グラフを作る再帰手続き
void alltopo(OrderDictionary *orders, // 既知の擬順序
const AdjacencyMatrix &prev_ord, // 辺(u,v)を追加する前の擬順序
vertex_t u, vertex_t v)
{
// まず辺(u,v)を追加しない場合を再帰的に探索
if (v == u-1) {
if (u != N_VERT-1)
alltopo(orders, prev_ord, u, v+2);
} else if (v == N_VERT-1) {
alltopo(orders, prev_ord, u+1, 0);
} else {
alltopo(orders, prev_ord, u, v+1);
}
// 次に辺(u,v)を追加する場合を検証
if (prev_ord.test(u,v)) // uからvへの経路が既に存在すれば直ちに枝刈り
return;
#ifdef SKIP_T0
if (prev_ord.test(v,u)) // ループが出来る場合はT0空間にならない
return;
#endif
// 頂点sからu、vからtへの経路が元々存在すればsからv,tにも行けるようになるので、
// それに対応する擬順序を生成する
AdjacencyMatrix ord = prev_ord;
row_t to_v_and_later = prev_ord.row[v] | (1U<<v);
for (vertex_t s = 0; s != N_VERT; ++s) {
if (s == u || prev_ord.test(s,u))
ord.row[s] |= to_v_and_later;
}
263:256
08/10/16 01:00:11
// 得られた擬順序と同じものがordersにまだ登録されていなければ登録する
std::pair<OrderDictionary::iterator, bool> insert_result = orders->insert(ord);
if (!insert_result.second) // 既に同じ擬順序が登録済みなら枝刈り
return;
// 次に分岐する辺と新しい擬順序を与えて再帰的に探索
if (v == u-1) {
if (u != N_VERT-1)
alltopo(orders, ord, u, v+2);
} else if (v == N_VERT-1) {
alltopo(orders, ord, u+1, 0);
} else {
alltopo(orders, ord, u, v+1);
}
}
264:256
08/10/16 01:01:46
int main(int argc, char *argv[])
{
OrderDictionary orders;
AdjacencyMatrix initial_adj; // 空の擬順序からスタート
initial_adj.clear();
orders.insert(initial_adj);
alltopo(&orders, initial_adj, 0, 1); // 辺(0,1)から順に分岐
265:256
08/10/16 01:02:39
// 以下出力ルーチン
OrderDictionary::const_iterator p = orders.begin(), endp = orders.end();
unsigned int count = 0;
while (p != endp) {
OrderDictionary::const_iterator q = p;
do {
++q;
++count;
} while (q != endp && count % 8);
for (unsigned int u = 0; u != N_VERT; ++u) {
for (OrderDictionary::const_iterator r = p;;) {
for (unsigned int v = 0; v != N_VERT; ++v)
std::cout << (r->test(u,v) ? '1' : '0');
if (++r == q)
break;
std::cout << ' ';
}
std::cout << '\n';
}
std::cout << '\n';
p = q;
}
std::cout << count << " total\n";
return 0;
}
266:１３２人目の素数さん
08/10/16 08:51:48
さあああああああああああああああああああああああああんくす
267:１３２人目の素数さん
08/10/16 12:44:02
あげしうまい
268:１３２人目の素数さん
08/10/28 20:02:43
chk
269:１３２人目の素数さん
08/12/03 12:48:19
377
270:１３２人目の素数さん
09/01/11 08:54:09
653
271:１３２人目の素数さん
09/02/06 08:16:34
196
272:１３２人目の素数さん
09/02/08 09:25:05
age
273:１３２人目の素数さん
09/02/09 20:27:18
有限個
274:１３２人目の素数さん
09/04/25 11:06:35
744
275:１３２人目の素数さん
09/06/21 20:43:30
459
276:１３２人目の素数さん
09/07/11 01:15:56
815