piDD 置換DD

• 置換集合向けの決定木ダイアグラムpiDD
  • 資料１
  • 資料２
• BDD/ZDDは組み合わせ集合の空間の部分をうまく表現する仕組み
  • BDDの構成アルゴリズム
  • BDDをべたべたにRで書いてみようこちら
• piDDは置換(順列)の集合の空間の部分をうまく表現する仕組み(らしい)
• ルービックキューブの手順はpiDD表現できる
• 組合せ→置換(順列)→群論
• piDD の主な演算
  • Union
  • Intersection
  • Difference
  • special Cartesian product
• 置換の合成
  • (1,2,3,4)->(4,2,1,3)と言う置換を

p <- c(4,2,1,3)

• • と表すと、p1して次にp2する(p1　p2の合成)は

comp.pi <- function(p1,p2){
	p2[p1]
}
k <- 4
p1 <- sample(1:k)
p2 <- sample(1:k)
comp.pi <- function(p1,p2){
	p2[p1]
}
k <- 4
p1 <- sample(1:k)
p2 <- sample(1:k)
p1
p2
comp.pi(p1,p2)

> p1
[1] 4 3 2 1
> p2
[1] 3 4 2 1
> comp.pi(p1,p2)
[1] 1 2 4 3

• 単位置換：

k<-4
pe <- 1:k

• 置換のdimension
  • 置換のdimensionを、「動かされる要素のうち最大のもの」とする
  • 単位置換のdimsnsionを０とするようにちょっと工夫しておく

dim.pi <- function(p){
	max(c(0,which(p-(1:length(p))!=0)))
}

p1 <- c(sample(1:4),5:8)
p1
dim.pi(p1)
dim.pi(1:4)

dim.pi <- function(p){
	max(which(p-(1:length(p))!=0))
}

p1 <- c(sample(1:4),5:8)
p1
dim.pi(p1)

> p1 <- c(sample(1:4),5:8)
> p1
[1] 4 1 3 2 5 6 7 8
> dim.pi(p1)
[1] 4
> dim.pi(1:4)
[1] 0

• 置換の省略表記
  • (3,5,2,1,4,6,7,8)という置換のdimensionは 5 で、(3,5,2,1,4)という情報だけで十分なので、dimension分の長さだけを書くことにする
  • また、置換のセットを問題にするので、のような表記をする。これはを表している
• 置換集合のdimension
  • 置換集合のdimensionは置換集合の要素である置換のdimensionの最大値