再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (1)

この記事では、与えられた数字の並びの次に大きい並べ替えを得る方法(アルゴリズム)と、それを応用して再帰呼び出しを使わずに順列や組合せを得るC言語プログラムを紹介します。

並べ替え

まず、同じ数字が含まれたn個の数字の並べ替えについて考えます。

実行結果

プログラムの実行結果は、次の通りです。4つの数0,1,1,2を並べ替えたものです:

0112
0121
0211
1012
1021
1102
1120
1201
1210
2011
2101
2110

プログラム

C言語のソースプログラムは、以下の通りです:

#include <stdio.h>

/* 与えられた並びpの次に大きい並べ替えを返す */
int next_perm(int *p, int n)
{
  int i, j, k, tmp;

  /* 上位桁のほうが下位桁よりも小さいところまで移動 */
  for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);

  /* pが最大(次の並べ替えがない) */
  if(i == 0) return 0;

  /* p[i-1]より値の大きい最も下位の桁をp[j]とする */
  for(j = n - 1; j > i && p[i-1] >= p[j]; j--);

  /* p[i-1]とp[j]とを交換 */
  tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;

  /* p[i]から最下位までを逆順 */
  for(k = 0; k <= ((n-1)-i)/2; k++)
    tmp = p[i+k], p[i+k] = p[(n-1)-k], p[(n-1)-k] = tmp;

  return 1;
}

int main(void)
{
  int p[4] = {0, 1, 1, 2};
  int i;

  /* 並べ替え */
  do {
    for(i = 0; i < 4; i++)
      printf("%d", p[i]);
    printf("\n");
  } while(next_perm(p, 4));

  return 0;
}

next_perm関数は、数字の並びを与えると、その次に大きい並べ替えを返すというものです。最小のものから出発し、次々とnext_perm関数を適用すると、いずれは最大のものに到達し、結果的にすべての並べ替えが得られます。

next_perm関数には配列pのポインタが渡されるため、do~while文の条件部分が実行されるたびに配列pが次の並べ替えに書き換えられます。

アルゴリズム

以下の手順で、与えられた数字の並びpの次の大きさの並べ替えが得られます。

  1. 最下位桁から出発して、上位桁のほうが下位桁よりも小さいところまで移動し、そこをp[i-1]とする。
  2. p[i]が最上位桁(つまり、i = 0)なら、与えられた並びが最大なので終了。
  3. p[i-1]より値の大きい最も下位のものをp[j]とする。
  4. p[i-1]とp[j]を交換する。
  5. p[i]以下の桁を逆順にする。

4つの数0,1,1,2の並べ替えの中では、2,1,1,0が最大です。2番目のステップは、与えられた数字の並びが2,1,1,0に一致するかどうかの判定です。一致すれば最大なので次の並べ替えはありません。

具体例として、1,0,2,1を考えてみます。1番目のステップでi = 2, p[i] = 2となります。2番目のステップの条件は満たされないので次のステップへ。3番目のステップでj = 3, p[j] = 1となります。4番目のステップで1,1,2,0が得られ、さらに5番目のステップで1,1,0,2が得られます。これが、1,0,2,1の次に大きい並べ替えです。

順列

順列とは、相異なるn個のものからr個を取って一列に並べた組です。列の構成要素の個数を順列の長さといいます。構成要素が同じでも、並べる順序が違えば区別します。この意味での順列は、置換とも呼ばれます。なお、順列という言葉が用いられるとき、並べ方の数を指すこともあります。

上の並べ替えにおいて、すべての数字が異なるときが、n=rのときの順列になります。

次回につづく。

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示