アルゴリズムの全探索における完全列挙の表示を行う可能な限り単純なプログラムを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: 完全列挙表示プログラム
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 を表示していません。
表示のルールがよくわかりません。
もう少し厳密にルールを記述してください。
あるいは、表示例を適切なものにしてください。
完全列挙するだけなら、戻りは表示しなくてよいのではありませんか?
ルールに明確であれば、コードを書くのは簡単です。
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: 完全列挙表示プログラム
表示のルールを明確にしなければコードが書けないといっているに、
表示のルールを明確にしてもらえないのはなぜでしょうか?
しかたがないので、次のように決めさせてもらいました。
1 から n までの数字を 1つずつ使用し、それらを最大 n 個まで並べて表示する。
ただし、n 個に満たない場合、後続には 0 を補う。重複は許さない。
n が大きいと表示の個数が爆発的に増加するため、
実際には、n は 10程度が限界となります。
表示のルールを明確にしてもらえないのはなぜでしょうか?
しかたがないので、次のように決めさせてもらいました。
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 は 10程度が限界となります。
Re: 完全列挙表示プログラム
返信が遅れてしまい申し訳ございません
ルールは「同じ並びは省略する」とし、また、完全列挙の表示だけですので0は補わず次のような形にしたいと思っています。
------------
n =3のとき
1
12
123
13
132
2
21
213
23
231
3
31
312
32
321
-------------
こちらの事情で直ぐに反応出来ず本当に申し訳ございません。
ルールは「同じ並びは省略する」とし、また、完全列挙の表示だけですので0は補わず次のような形にしたいと思っています。
------------
n =3のとき
1
12
123
13
132
2
21
213
23
231
3
31
312
32
321
-------------
こちらの事情で直ぐに反応出来ず本当に申し訳ございません。
Re: 完全列挙表示プログラム
ユーザ名が間違っています。自分の名前を書いてください。
コードが理解できませんか?
for (int k = 0; k < n; k++) printf(" %d", a[k]);
を
for (int k = 0; k <= i; k++) printf(" %d", a[k]);
に変えれば済む話では?
コードが理解できませんか?
for (int k = 0; k < n; k++) printf(" %d", a[k]);
を
for (int k = 0; k <= i; k++) printf(" %d", a[k]);
に変えれば済む話では?