bincombinations から n-combinations まで

R の e1071 ライブラリに bincombinations がある。

bincombinations(3) で，2^3 × 3 行列の結果が返される。

> bincombinations(3)
     [,1] [,2] [,3]
[1,]    0    0    0
[2,]    0    0    1
[3,]    0    1    0
[4,]    0    1    1
[5,]    1    0    0
[6,]    1    0    1
[7,]    1    1    0
[8,]    1    1    1

要するに，n 桁の 2 進数の各桁が 2^n 行で表される。ただ，これだと結果が行列で返されるので，不都合な場合もある。また，一般に n 進数の結果が必要になることもある。bincombinations を一般化するのは，このページの下の方に再掲載しておく。

まず，与えられた n 進数表記の次の数の表記を与える関数を書いてみる。

next.Ncombination = function(x, base=2) {
  n = length(x)
  carry = 0
  x[n] = x[n] + 1
  for (i in n:1) {
    x[i] = x[i] + carry
    carry = 0
    if (x[i] >= base) {
      x[i] = 0
      carry = 1
    }
  }
  return(x)
}

この関数を

n = 4
base = 2
x = integer(n)
for (i in seq.int(base ^ n)) {
  print(x)
  x = next.Ncombination(x, base)
}

のように指定すると全ての組み合わせが得られる。bincombinations(4) と同じであるが，それぞれの結果はベクトルである。

[1] 0 0 0 0
[1] 0 0 0 1
[1] 0 0 1 0
[1] 0 0 1 1
[1] 0 1 0 0
[1] 0 1 0 1
[1] 0 1 1 0
[1] 0 1 1 1
[1] 1 0 0 0
[1] 1 0 0 1
[1] 1 0 1 0
[1] 1 0 1 1
[1] 1 1 0 0
[1] 1 1 0 1
[1] 1 1 1 0
[1] 1 1 1 1

上の使用例の print 文の位置に必要な処理プログラムを書けばよい。

tricombinations に相当するプログラムは base = 3 とするだけでよい。

> n = 4
> base = 3
> x = integer(n)
> for (i in seq.int(base ^ n)) {
+   print(x)
+   x = next.Ncombination(x, base)
+ }
[1] 0 0 0 0
[1] 0 0 0 1
[1] 0 0 0 2
[1] 0 0 1 0
[1] 0 0 1 1
[1] 0 0 1 2
[1] 0 0 2 0
[1] 0 0 2 1
[1] 0 0 2 2
   中略
[1] 2 2 1 1
[1] 2 2 1 2
[1] 2 2 2 0
[1] 2 2 2 1
[1] 2 2 2 2

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

オリジナルの bincombinations のソースプログラム

bincombinations = function (p) {
    retval = matrix(0, nrow = 2^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))),
            length = 2^p)
    }
    retval
}

これを書き換えて，3, 4, 5, ... 進数に対応させた tricombinations, quatrcombinations, ... quintcombinations など

tricombinations = function(p) {
    retval = matrix(0, nrow = 3^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (3^p/3^n)), rep(1, (3^p/3^n)), rep(2, (3^p/3^n))),
            length = 3^p)
    }
    retval
}

quatrcombinations = function(p) {
    retval = matrix(0, nrow = 4^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (4^p/4^n)), rep(1, (4^p/4^n)), rep(2, (4^p/4^n)), rep(3, (4^p/4^n))),
            length = 4^p)
    }
    retval
}

quintcombinations = function(p) {
    retval = matrix(0, nrow = 5^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (5^p/5^n)), rep(1, (5^p/5^n)), rep(2, (5^p/5^n)), rep(3, (5^p/5^n)), rep(4, (5^p/5^n))),
            length = 5^p)
    }
    retval
}

sextetcombinations = function(p) {
    retval = matrix(0, nrow = 6^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (6^p/6^n)), rep(1, (6^p/6^n)), rep(2, (6^p/6^n)), rep(3, (6^p/6^n)), rep(4, (6^p/6^n)), rep(5, (6^p/6^n))),
            length = 6^p)
    }
    retval
}

septetcombinations = function(p) {
    retval = matrix(0, nrow = 7^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (7^p/7^n)), rep(1, (7^p/7^n)), rep(2, (7^p/7^n)), rep(3, (7^p/7^n)), rep(4, (7^p/7^n)), rep(5, (7^p/7^n)), rep(6, (7^p/7^n))),
            length = 7^p)
    }
    retval
}

あとは，ご自由に定義してください