e1071:::permutations の代替関数 next.permutation

e1071 ライブラリには permutations 関数がある。

permutations は処理が速いが，配列で返すために大きなメモリーを消費する。

時間はかかってもよいので，メモリー消費のない関数が必要なこともある。そのようなときのために以下の関数を書いた。

next.permutation = function(x) {
  n = length(x)
  pos1 = 0
  for (i in (n - 1):1) {
    if (x[i] < x[i + 1]) {
      pos1 = i
      break
    }
  }
  if (pos1 == 0) {
    return(0)
  }
  for (i in n:(pos1 + 1)) {
    if (x[pos1] < x[i]) {
      pos2 = i
      break
    }
  }
  temp = x[pos1]
  x[pos1] = x[pos2]
  x[pos2] = temp
  len = (n - pos1) %/% 2
  if (len >= 1) {
    for (i in 1:len) {
      temp = x[pos1 + i]
      x[pos1 + i] = x[n - i + 1]
      x[n - i + 1] = temp
    }
  }
  return(x)
}

使用法は以下のように，最初に x に 1, 2, 3, ..., n をセットして，「x を使った処理」の次に必要な処理をプログラムする。

単に print(x) とするならば，可能な順列を全て列挙してくれる。

x = 1:4
while (TRUE) {
  # x を使った処理
  print(x)
  x = next.permutation(x)
  if (length(x) == 1) {
    break
  }
}

> x = 1:4
> while (TRUE) {
+   # x を使った処理
+   print(x)
+   x = next.permutation(x)
+   if (length(x) == 1) {
+     break
+   }
+ }
[1] 1 2 3 4
[1] 1 2 4 3
[1] 1 3 2 4
[1] 1 3 4 2
　　　:
[1] 4 2 1 3
[1] 4 2 3 1
[1] 4 3 1 2
[1] 4 3 2 1