組合せ

組合せ部分集合の族に見られる団代数

要素数nの集合の部分集合の族は個の部分集合からなり、それらの包含関係は超立方体の形をしたポセットになっている このポセットを無向グラフと見ると、n正則グラフになっている 見方を変える n本の紐を互いに1度ずつだけ交叉させて、紐の順序を1,2,3,...,n…

複体の数と列挙

要素があるときに、集合族を考えて、さらにその中で複体制約を満足することを考える さらに、複体であって、がすべて複体を構成する単体に帰属するものとする その個数はこちらに書いたように、数列ID:A006126 "Number of hierarchical models with linear t…

積:グラフ代数

積 デカルト積 グラフのデカルト積は、の順序対をノードとして、のときにはを辺に持ち、また、のときにはを辺に持つようなグラフ # グラフ(とその隣接行列)を適当に作り g1 <- make.graph.adj(5) g2 <- make.graph.adj(4) gr.dec.prod <- function(m1,m2){ n…

和:グラフ代数

和 直和 結び 有向結び 和の法則 , , , , X <- matrix(c(0,1,1,1,0,0,1,0,0),byrow=TRUE,3,3) Y <- matrix(c(0,1,1,1,0,1,1,1,0),byrow=TRUE,3,3) sum.graph <- function(X,Y){ dimX <- dim(X) dimY <- dim(Y) Z <- matrix(0,dimX[1]+dimY[1],dimX[2]+dimY[2…

線グラフ(line graph)からハイパーグラフへ:グラフ代数

グラフと線グラフとについて前記事に書いた 要素集合があったとき、 いわゆるグラフのノードは個々の要素 いわゆるグラフのエッジは個々の要素のペア 線グラフのノードはいわゆるグラフのエッジに対応して、それは要素のペア 線グラフのエッジはいわゆるグラ…

線グラフ(line graph):グラフ代数

Line graphは無向グラフのエッジをノードに置き換え、頂点をエッジに置き換えたもの(Wiki) ひとまずRでたどって処理を追ってみる # 適当にグラフオブジェクトとその隣接行列を作る g <- make.graph.adj(5) # 補助関数 # ベクトルの要素ごとにxor(),&関数を適…

補グラフ:グラフ代数

ぱらぱらめくる『クヌース本4.0』から 補グラフ , それぞれの隣接行列をとする ,ただしは要素がすべて1の正方行列、は単位行列。は完全グラフの隣接行列 ブール代数っぽく、隣接行列をTRUE,FALSEにしてやってみよう 補グラフを作ることは、隣接行列のブール…

ぱらぱらめくる『クヌース本4.0』

The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se)作者: Donald E. Knuth,和田英一出版社/メーカー: アスキー・メディアワークス発売…

BDD/ZDD

日本語総説はこちら 組合せ発散に対する、この方法の効果はこちらの動画と実行例コードで BDD:binary decision diagram 個の2分岐がの場合を作る。それを表したのが二分決定木(binary decision tree) BDDは二分決定木を簡略したグラフ の3分岐の「○、×」が…

順序をつける

前稿では、複数要素を2群に分けてスコアをつけるという判断方法で考えた そうしているかどうかの保証はない こんなやり方はどうだろうか? 複数の要素がある。全部に順序をつけるのは難しいから、一部を取り出して、その中に順序をつける。一部の取り出し方…

2群に分ける

こちらで、選択について書いた。選択肢には適切な数があって、その数は、6や7らしい。個人差はあるものの5から9とか この5から9とはどういう数なのか 今、n.sample個の比較対象があって、それらを「○、×」に分ける指標がn.axis個あるとする ○の数が一…

夢中に解くときのの組み合わせ解法は?

こんなニュースがありました 『ゲーマー、科学の難問クリア…たんぱく質の形』→こちら この記事で紹介されているソフトはFoldIt→こちら こんがらがった紐をほどくっていうのも、結構、いつの間にか、ほどけたりします。これも同じ