三輪車の再発明

nCr列挙プログラム(＜まだやってたんか、、

/** f_から始まる増分1の等差数列n_項を、
 *  (n_+1)div 2個とn_ div 2個に分割する組み合わせを列挙するプログラム
 */
enum {
  f_ = 5,     /* 初項の値 */
  n_ = 5      /* 項数 */
};

a[n_+1], t;

/* fから始まる増分1の等差数列n項から、昇順にr項取り出す組み合わせを列挙 */
void select(f, n, r, j)
{
  int d, i, k;

  if (r == 0) {
    /* 取り出した要素の表示 */
    printf("(");
    for (i = 0; i < j; ++i)
      printf("%d ", a[i]);
    printf("),(");
    /* 残った要素の表示 */
    t = f_;
    a[j++] = f_ + n_;
    for (i = 0; i < j; ++i) {
      for (k = t; k < a[i]; ++k)
        printf("%d ", k);
      t = a[i] + 1;
    }
    puts(")");
    return;
  }
  d = n - r + 1;
  for (i = 0; i < d; ++i) {     /* 最初の要素を先頭d個から選ぶ */
    t = f + i;
    a[j] = t;
    select(t + 1, n - i - 1, r - 1, j + 1);
  }
}

main()
{
  int r;

  r = (n_ + 1)/2;  /* 2分割のサイズ(大きいほう) */
  select(f_, n_, r, 0);
}

これはこれで動くが、このままでは末尾再帰に持ち込めない悪寒。再帰呼び出しを除去するには次の選択肢しかなさげ。

1. rの上限決め打ち (上限をr_maxとして、r_max重の多重ループにする)
2. スタックの導入

別にA面ダイス問題の答えを列挙するだけなら、r≦10のケースだけなはずなんで多重ループにしてもいいんですけども、上のやり方よりかえって記述量増えそう＿|￣|○|||

それはそうと、今朝方ふと思いついて次のコードを試してみた。惜しい動作だった(全解列挙におよばず)。

const int f_ = 5;          /* 先頭要素の値(以降、増分1の等差数列とする) */
const int n_ = 5;          /* 要素数 */

a[10], b[10];
c, d, f, i, j, k, m, n, r, s, t, x;

/* fから始まる増分1の等差数列n項から、sに従って昇順にr項取り出す */
select(f, n, r, s)
{
  if (r == 0)
    return;
  d = n - r + 1;
  t = s%d; /* s/dのι゛ょ ぅょ */
  s /= d;
  x = f + t;
  a[j++] = x;
  for (i = t; i; --i)
    b[k++] = x - i;
  select(x+1, n - t -1, r-1, s);
}

main()
{
  r = (n_ + 1)/2;  /* 2分割のサイズ(大きいほう) */
  m = (5 * 4 * 3) / (3 * 2 * 1);  /* nCr; n=5, c=3 */
  for (s = 0; s < m; ++s) {
    j = k = 0;
    select(f_, n_, r, s);
    for (i = a[r - 1] + 1; i < f_ + n_; ++i)
      b[k++] = i;
    printf("(");
    for (i = 0; i < r; ++i)
      printf("%d ", a[i]);
    printf("),(");
    for (i = 0; i < n_-r; ++i)
      printf("%d ", b[i]);
    puts(")");
  }
}

こっちの再帰なら問題なくループにできるのに、、
うまくいかない理由は数論的な何か(s/dのι゛ょ ぅょが全ての組み合わせを舐めてくれない)。
s/dのι゛ょ ぅょを利用して、整数(0〜nCr - 1)を具体的な解の集合に写像する試みは失敗した、、