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

前回の続き。再帰呼び出しを使わずに、n個の数からr個を取り出して並べる順列を得るC言語プログラムの紹介。

n個の数からr個を取り出して並べる順列

実行結果

実行結果は、次の通りです。4つの数0,1,2,3から2個を取り出して並べ順列を求めています。

0123
0213
0312
1023
1203
1302
2013
2103
2301
3012
3102
3201

この実行結果は、p[0]~p[n-1] (この実行結果ではp[0]~p[3])を並べたものになっています。そのうち、p[0]~p[r-1] (この実行結果ではp[0]~p[1])に求める結果が格納されています。

プログラム

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

#include <stdio.h>

/* 部分配列を降順にソート */
void rev_sort(int *p, int from, int to)
{
  int i, j, tmp;

  for(i = from + 1; i <= to; i++)
    for(j = i; j >= from + 1 && p[j-1] < p[j]; j--)
      tmp = p[j], p[j] = p[j-1], p[j-1] = tmp;
}

/* n個の中からr個取り出す順列の中で、
   与えた順列pの次に大きいものを返す */
int next_perm(int *p, int n, int r)
{
  int i, j, k, tmp;

  if(r <= 0 || n < r) return 0;

  /* r桁より下を降順にソート */
  rev_sort(p, r, n-1);

  /* 上位桁のほうが小さいところまで移動 */
  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, 2, 3};
  int i;

  /* 順列の列挙 */
  do {
    for(i = 0; i < 4; i++)
      printf("%d", p[i]);
    printf("\n");
  } while(next_perm(p, 4, 2));

  return 0;
}

アルゴリズム

左からr+1番目以降の並べ替えが省略できれば、r個(r<n)を選んで並べる場合に対応できます。それを実現するには、前回紹介したアルゴリズムに「左からr+1番目以下を降順にソートする」という1ステップを追加すれば十分です。

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

次回につづく。

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

プロフィール

よしいず

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

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

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

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

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

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