？？？有限集合に位相はいくつ入るか？？？at MATH？？？有限集合に位相はいくつ入るか？？？ - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞのURL■項目テキスト256:１３２人目の素数さん 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; 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch