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

再帰による組み合わせ列の生成; {0, 1} の場合

R

[1] の文献をかなり参考にさせていただきました。
少し修正して、配列を演算に使えるようにしています。
でも、かなり小標本じゃないと使えないですよねぇ。

shuffer <- function(n, m) {
  m <- as.integer(m)
  n <- as.integer(n)
  if (m > n) {
    tmp <- m; m <- n; n <- tmp
    warning("n must be large than m; result that was exchanged n for m is shown.")
  }
  counter <<- 0
  btrace(0, 1, m, n - m, rep(0, n))
  cat(sprintf("Count: %d\n", counter))
  cat(sprintf("choose(%d, %d) = %d\n", n, m, choose(n, m)))
}

btrace <- function(p, q, m, nm, t) {

  for (i in (p+1):(nm+q)) {
    t[i] <- 1
    if (m != q) {
      btrace(i, q + 1, m, nm, t)
    } else {
      counter <<- counter + 1
      print(t)
    }
    t[i] <- 0
  }

}

shuffer(5, 3)
shuffer(3, 5)
> shuffer(5, 3)
[1] 1 1 1 0 0
[1] 1 1 0 1 0
[1] 1 1 0 0 1
[1] 1 0 1 1 0
[1] 1 0 1 0 1
[1] 1 0 0 1 1
[1] 0 1 1 1 0
[1] 0 1 1 0 1
[1] 0 1 0 1 1
[1] 0 0 1 1 1
Count: 10
choose(5, 3) = 10

ちなみに、(n, m) にあまりでかい数を入れると大変なことになるので注意してください。

追記

e1071 package に permutations(n) や bincombinations(p) という関数もあります。
似た関数ですが、permutations(n) は {1, 2, ..., n} のすべての並べ替え列、bincombinations(p) は長さ p の {0, 1} の組み合わせ列をすべて生成します (上で書いた shuffer(p, 1), shuffer(p, 2), ..., shuffer(p, p) と同じ)。
早いらしい?