読者です 読者をやめる 読者になる 読者になる

廿TT

譬如水怙牛過窓櫺 頭角四蹄都過了 因甚麼尾巴過不得

n 人をふたつにわける組み合わせを列挙する

R

ふたつの組 A と B があり, a_i を i 番目の人を組 A に入れるとき 1, 入れないとき 0 を取る変数とする.

下のような樹形図で考えると, 2 値の変数が n 個あるので, 組み合わせの数の総数は  p=2^n .

f:id:abrahamcow:20161230180226p:plain
Binary Tree clip art Free Vector / 4Vector より)

なので最初に pn 列の行列を用意する.

a_1=1 に対応するように, 行列の上半分は 1, a_1=0 に対応するように行列の下半分は 0 とする.

分岐した先でも同じように上半分は 1, 下半分は 0 とする操作を繰り返す.

この操作を合計 n 回やれば, すべての組み合わせを重複なく列挙できる.

R のコードはこんな感じ.

make_binary_tree <- function(n){
  p =(2^n)
  mat <-matrix(,p,n)
  for(i in 1:(n-1)){
    mat[,i]=rep(c(TRUE,FALSE),each=p/(2^i))
  }
  mat[,n] <- c(TRUE,FALSE)
  return(mat)
}

image(1:5,1:(2^5),t(make_binary_tree(5)),xlab = "",ylab="")

f:id:abrahamcow:20161230185533p:plain

ふたつの組を区別しないことにすると, a_1=1 の場合だけを考えればよいので, こんな感じになる.

make_binary_tree_half <- function(n){
  p =(2^n)/2
  mat <-matrix(,p,n)
  mat[,1]=TRUE
  for(i in 1:(n-2)){
    mat[,i+1]=rep(c(TRUE,FALSE),each=p/(2^i))
  }
  mat[,n] <- c(TRUE,FALSE)
  return(mat)
}

image(1:5,1:((2^5)/2),t(make_binary_tree_half(5)),xlab = "",ylab="")

f:id:abrahamcow:20161230185814p:plain