完全列挙表示プログラム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
C言語初心者

完全列挙表示プログラム

#1

投稿記事 by C言語初心者 » 3週間前

アルゴリズムの全探索における完全列挙の表示を行う可能な限り単純なプログラムをC言語で作成したいのですが、どう書けばいいか分かりません。考えているのが、例えば1,2,3という3つの数があったとすると最後まで並べたら前に戻り別の並びを表示する表示例のような形にしたいです。

表示例
1 0 0
1 2 0
1 2 3
1 2 0
1 0 0
1 3 0
1 3 2
2 0 0
2 1 3
2 1 0
.
.
.
3 2 1

かずま

Re: 完全列挙表示プログラム

#2

投稿記事 by かずま » 3週間前

0 1 2 3 の 4つの数字を並べるのではなく、
1 2 3 の 3つの数字を 1文字、2文字、3文字の完全列挙ですね。
3文字に満たない場合、後続には 0 を補う。

1 2 3 まで行った後、戻って 1 2 0、1 0 0 を表示していますが、
1 3 2 まで行った後、戻りの 1 3 0、1 0 0 を表示していません。
表示のルールがよくわかりません。
もう少し厳密にルールを記述してください。
あるいは、表示例を適切なものにしてください。

完全列挙するだけなら、戻りは表示しなくてよいのではありませんか?
ルールに明確であれば、コードを書くのは簡単です。

かずま

Re: 完全列挙表示プログラム

#3

投稿記事 by かずま » 2週間前

表示のルールを明確にしなければコードが書けないといっているに、
表示のルールを明確にしてもらえないのはなぜでしょうか?

しかたがないので、次のように決めさせてもらいました。

1 から n までの数字を 1つずつ使用し、それらを最大 n 個まで並べて表示する。
ただし、n 個に満たない場合、後続には 0 を補う。重複は許さない。

コード:

#include <stdio.h>

#define N 12

int n, a[N], u[N+1];

void gen(int i)
{
	if (i < n)
		for (int j = 1; j <= n; j++)
			if (!u[j]) {
				a[i] = j, u[j] = 1;
				for (int k = 0; k < n; k++) printf(" %d", a[k]);
				putchar('\n');
				gen(i + 1);
				a[i] = 0, u[j] = 0;
			}
}

int main(void)
{
	while (printf("n: "), scanf("%d", &n) == 1) gen(0);
}
n が大きいと表示の個数が爆発的に増加するため、
実際には、n は 10程度が限界となります。

かずま

Re: 完全列挙表示プログラム

#4

投稿記事 by かずま » 2週間前

返信が遅れてしまい申し訳ございません
ルールは「同じ並びは省略する」とし、また、完全列挙の表示だけですので0は補わず次のような形にしたいと思っています。
------------
n =3のとき

1
12
123
13
132
2
21
213
23
231
3
31
312
32
321
-------------
こちらの事情で直ぐに反応出来ず本当に申し訳ございません。

かずま

Re: 完全列挙表示プログラム

#5

投稿記事 by かずま » 2週間前

ユーザ名が間違っています。自分の名前を書いてください。

コードが理解できませんか?

for (int k = 0; k < n; k++) printf(" %d", a[k]);

for (int k = 0; k <= i; k++) printf(" %d", a[k]);
に変えれば済む話では?

返信

“C言語何でも質問掲示板” へ戻る