順列を列挙する

Algorithm C

最近、ちょっとだけ独学を始めた C 言語を使って、順列 (permutation) を列挙するコードを書いてみようと思い立ちました。 少し前に読んだ 『Java データ構造とアルゴリズム基礎講座』(長尾和彦著 技術評論社 2009 ISBN978-4-7741-3697-4) という本で小さな疑問として残っていたものが、その後たまたま近所の書店で手にした 『プログラミングの宝箱 アルゴリズムとデータ構造 第2版』(紀平拓男, 春日伸弥著 ソフトバンク クリエイティブ 2011 ISBN978-4-7973-6328-9) という本の 「常に検索効率のよいツリー「平衡木」を作る」 と題したコラム (pp. 190 - 199) において触れられていたことが、きっかけでした。 なぜ、それが、順列を列挙するコードを書いてみようと思い立ったきっかけになったのかについては、書いてみると意外に長くなったので、いったん、これ以上は割愛します。

いきなりですが、現時点までに、わたしが書いたコードは、次のとおりです。

#include <stdlib.h>

int *getIntPerms(const int *elements, const int n, const int r, int *num) {
  int i, j, k;
  if (n < 1 || r < 0 || n < r) {
    *num = 0;
    return NULL;
  }
  if (r == 0) {
    *num = 1;
    return NULL;
  }
  int *res;
  if (r == 1) {
    res = (int *)malloc(n * sizeof(int));
    for (j = 0; j < n; j++)
      *(res + j) = *(elements + j);
    *num = n;
    return res;
  }
  int *e, *nums[n], *p[n];
  e = (int *)malloc((n - 1) * sizeof(int));
  *num = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < i; j++)
      *(e + j) = *(elements + j);
    for (j = i; j < n - 1; j++)
      *(e + j) = *(elements + j + 1);
    nums[i] = (int *)malloc(sizeof(int));
    p[i] = getIntPerms(e, n - 1, r - 1, nums[i]);
    *num += *nums[i];
  }
  free(e);
  res = (int *)malloc(*num * r * sizeof(int));
  for (i = 0; i < n; i++) {
    for (j = 0; j < *nums[i]; j++) {
      *(res + i * *nums[i] * r + j * r) = *(elements + i);
      for (k = 1; k < r; k++)
        *(res + i * *nums[i] * r + j * r + k) = *(p[i] + j * (r - 1) + k - 1);
    }
    free(p[i]);
    free(nums[i]);
  }
  return res;
}

変数名の付け方がいけないのか、getIntPerms 関数の引数リスト等の定義がいけないのか、あるいは、処理の流れがいけないのか、よくわからないのですが、かなり細かくコメントを書かないと、たぶん何をやろうとしているのか後で見て理解するのに苦労するんじゃないか、という気がします。

どうしても直感的には汚いコードだなあという感触が拭えず、ときどき最初から白紙の状態から書き始めてみたりもしたのですが、ふと気づくと、だいたい似たようなコードになってしまいます。 いまのところ、自分には、この程度が限界なのかもしれません。

ちなみに、getIntPerms 関数で何をしようとしているのかというのを説明しますと、引数のうち n と r は、順列をあらわす数式 nPr の n と r をそれぞれ指します。 n!/(n-r)! とあらわされることの多い、順列の総数は、引数 num があらわすポインタの指す場所に格納されます。 そして、この関数の戻り値となるポインタの指す場所には、列挙されたすべての順列パターンが格納されます。

うーむ、これはまいった。 日本語で説明すること自体、うまくできていない気がします。

上記を利用するコードは、たとえば次のようになりましょうか。

#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int data[5];
  data[0] = 0;
  data[1] = 1;
  data[2] = 2;
  data[3] = 3;
  data[4] = 4;
  int *p;
  int n;
  int r;
  int x;
  n = 5;
  r = 5;
  p = getIntPerms(data, n, r, &x);
  int i;
  for (i = 0; i < x; i++) {
    int j;
    for (j = 0; j < r; j++)
      printf(" %d", *(p + i * r + j));
    printf("\n");
  }
  free(p);
  printf("\nNumber of permutations = %d\n", x);
}

たとえば、5 個の要素から 5 個を選び出す場合の順列の総数は 120 となります。 上記のコードを実行すると、120 個のパターンが、以下のように列挙されます。

$ ./perm.exe
 0 1 2 3 4
 0 1 2 4 3
 0 1 3 2 4
 0 1 3 4 2
 0 1 4 2 3
 0 1 4 3 2
 0 2 1 3 4
 0 2 1 4 3
 0 2 3 1 4
 0 2 3 4 1
 0 2 4 1 3
 0 2 4 3 1
 :
(中略)
 :
 4 3 0 1 2
 4 3 0 2 1
 4 3 1 0 2
 4 3 1 2 0
 4 3 2 0 1
 4 3 2 1 0

Number of permutations = 120

もともとのコードでは、おそらく最初に誰でも思いつくような再帰的な処理をおこなっています。 これとは異なる、もっと奇抜で美しくてわくわくするようなアルゴリズムはないものかな、などと思ったりもしているのですが、それ以前に、どうして自分が書くコードはこれほどまでにも読みづらいのだろうかと、そっちのほうがまずは問題だったりします。

まとめ

以上、誰かに読んでいただく日記ではなく、あとで恥ずかしくも懐かしく思うための素材として、あえてここに書き残すことにしました。