配列に順列を入れ、その順列を使いルール通りの組合せを作るには

配列nを用意して、２*nの配列に1～Ｚ、又は１～９までの数字を格納します。３の場合、123,132,213,231,312,321の順列で、ルールは１の時は１つ間を空けて１を、２の時は２つ間を空けて２を・・・
つまり、３の場合は　231213,312132　の二つがルールと合致しているので答えとなります。
１～Ｚまでで、上記のようにルールに当てはまる場合のみを出力するプログラムを書きたいのですがうまくいきません。下に考えてみたものを載せます。どなたか分かる方ご教授願います。

#include<stdio.h>
int p[99]={0},a[99]={0};
int n;
int count;
main(){
int i;
void perm(int k);
while(1){
scanf("%d",&n); if(n<=0){break;}
for(i=1;i<=n;i++){p[i]=i;}
count=0;
perm(1);
}
}
void perm(int k){
int i,w;
if(k>n){
count++;
for(i=1;i<=n;i++){a[i]=p[i];}
for(i=1;i<=n;i++){a[i+a[i]+1]=a[i];}
printf("[%d]:",count);
for(i=1;i<=2*n;i++){printf("%3d",a[i]);} printf("\n");
}

else{
for(i=k;i<=n;i++){
w=p[k];p[k]=p[i];p[i]=w;
perm(k+1);
w=p[k];p[k]=p[i];p[i]=w;
}
}
}

No.4 回答者： tea_sheep 回答日時： 2007/04/21 18:06

確かに、要素数が3ないし5程度であれば、前半部分と後半部分でそれぞれ順列の

並び替えを行って、すべての場合について総当たりで調べることは可能でしょう。
しかし、たかだか9個だけでも、組み合わせ数は非現実的なものとなります。
1～9を用いるとすると、前半部分が9!(9の階乗)通り、同じく後半部分も9!通りで、
全組み合わせ数は (9!)×(9!)＝約1300億通り。
総当たり法ではどのくらいの時間がかかるのか見当も付きません…。

というわけで、順列の並び替えではなく、別の手段で組み合わせ数を減らしていく
ことをお勧めします。
例えば、前半部分だけを見た場合、ルールにマッチするのは1文字目が8または9の
場合だけで、1～7になることは有り得ませんよね。
同様に2文字目は7～9のどれかになりますね（しかも1文字目と同じ数字は含まない）。
そう考えていくと、前半部分でルールにマッチする並びというのはかなり限られた
数に絞り込めると思います。
後半部分についても同様に絞り込めますね。
というより前半部分を逆並びにするだけですが。
あとはそれら前半と後半を組み合わせて、ルールにマッチしているかどうか調べます。

No.3 回答者： SAKENOSAKA 回答日時： 2007/04/19 23:09

まだ理解し切れなく申し訳ない。

でもこれはちょっと難しいわ。
色々考えてみたけど一筋縄ではいかんぽい。

(1)順列を格納する
(2)解の全ての組み合わせ(しかも可変長)を出力する

(2)より(1)の方が難しくて、ちょっとお手上げ…。
そこで、このアルゴリズムを切り分けて考えるようにして
(1)についてもう一度、新規で質問を投稿することをお勧めします。

中途半端な回答になってしまい申し訳ありません。

この回答へのお礼

お手数おかけしてすいません。
順列の格納と出力は以前のソースで出来ていると思ってたのですが。

n=3　の場合

a[0] a[1] a[2] の配列を用意

2*n　なので

a[0] a[1] a[2] a[3] a[4] a[5]
1 2 3 0 0 0
1 3 2 0 0 0
2 1 3 0 0 0
2 3 1 0 0 0
3 2 1 0 0 0
3 1 2 0 0 0

#include<stdio.h>
int p[99]={0},a[99]={0};
int n;
int count;
main(){
int i;
void perm(int k);
while(1){
scanf("%d",&n); if(n<=0){break;}
for(i=1;i<=n;i++){p[i]=i;}
count=0;
perm(1);
}
}
void perm(int k){
int i,w;
if(k>n){
count++;
printf("[%d]:",count);
for(i=1;i<=2*n;i++){printf("%3d",p[i]);} printf("\n");
}

else{
for(i=k;i<=n;i++){
w=p[k];p[k]=p[i];p[i]=w;
perm(k+1);
w=p[k];p[k]=p[i];p[i]=w;
}
}
}

上記のソースから、（２）の組合せである
2 3 1 0 0 0
3 1 2 0 0 0
を
2 3 1 2 1 3
3 1 2 1 3 2
と出来ればと思っていたのですが。
色々と考えて頂きありがとうございました。

お礼日時：2007/04/19 23:45

No.2 回答者： SAKENOSAKA 回答日時： 2007/04/19 19:12

ルールに当てはまる場合のみを出力する

ということはだいたいわかるのですが
(前回はこの部分に特化した話です)

それ以前に
２*nの配列に1～Ｚ、又は１～９までの数字を格納します。
こちらがわの格納ルールはどういうルールで順列が格納されているのか
がちょっとわかりずらいです。3の場合しかないので

scanf("%d",&n);
for(i=1;i<=n;i++){p[i]=i;}
あなたが考えたプログラムをみると

入力された数字の分までの配列に順数を入れています。
たとえばn=3 p[] ={0,1,2,3}
というような結果になるソースを記載されているようですが
説明ではn=3 p[] ={123,132,213,231,312,321}
という状態になるべきだと理解してしまいます。
上と下とでは解法が変わってきます。

そこで、どういうルールで順列が格納されるべきなのかを
ハッキリさせて欲しいと思っています。

できれば5の場合の例を書いてもらうとわかると思います。

この回答への補足

再びありがとうございます。
（どういうルールで順列が格納されるべきなのか）
これは、n=3 p[] ={123,132,213,231,312,321}　という状態です。

５の場合というのは５の順列でしょうか？長くなりますが以下に
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 4 3
1 2 5 3 4
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 4 2
1 3 5 2 4
1 4 3 2 5
1 4 3 5 2
1 4 2 3 5
1 4 2 5 3
1 4 5 2 3
1 4 5 3 2
1 5 3 4 2
1 5 3 2 4
1 5 4 3 2
1 5 4 2 3
1 5 2 4 3
1 5 2 3 4
2 1 3 4 5
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 1 5 4 3
2 1 5 3 4
2 3 1 4 5
2 3 1 5 4
2 3 4 1 5
2 3 4 5 1
2 3 5 4 1
2 3 5 1 4
2 4 3 1 5
2 4 3 5 1
2 4 1 3 5
2 4 1 5 3
2 4 5 1 3
2 4 5 3 1
2 5 3 4 1
2 5 3 1 4
2 5 4 3 1
2 5 4 1 3
2 5 1 4 3
2 5 1 3 4
3 2 1 4 5
3 2 1 5 4
3 2 4 1 5
3 2 4 5 1
3 2 5 4 1
3 2 5 1 4
3 1 2 4 5
3 1 2 5 4
3 1 4 2 5
3 1 4 5 2
3 1 5 4 2
3 1 5 2 4
3 4 1 2 5
3 4 1 5 2
3 4 2 1 5
3 4 2 5 1
3 4 5 2 1
3 4 5 1 2
3 5 1 4 2
3 5 1 2 4
3 5 4 1 2
3 5 4 2 1
3 5 2 4 1
3 5 2 1 4
4 2 3 1 5
4 2 3 5 1
4 2 1 3 5
4 2 1 5 3
4 2 5 1 3
4 2 5 3 1
4 3 2 1 5
4 3 2 5 1
4 3 1 2 5
4 3 1 5 2
4 3 5 1 2
4 3 5 2 1
4 1 3 2 5
4 1 3 5 2
4 1 2 3 5
4 1 2 5 3
4 1 5 2 3
4 1 5 3 2
4 5 3 1 2
4 5 3 2 1
4 5 1 3 2
4 5 1 2 3
4 5 2 1 3
4 5 2 3 1
5 2 3 4 1
5 2 3 1 4
5 2 4 3 1
5 2 4 1 3
5 2 1 4 3
5 2 1 3 4
5 3 2 4 1
5 3 2 1 4
5 3 4 2 1
5 3 4 1 2
5 3 1 4 2
5 3 1 2 4
5 4 3 2 1
5 4 3 1 2
5 4 2 3 1
5 4 2 1 3
5 4 1 2 3
5 4 1 3 2
5 1 3 4 2
5 1 3 2 4
5 1 4 3 2
5 1 4 2 3
5 1 2 4 3
5 1 2 3 4

補足日時：2007/04/19 21:40

この回答へのお礼

失礼しました。
n=3 のとき、

p[0]=1
p[1]=2
p[2]=3

p[0]=1
p[1]=3
p[2]=2

というように配列の要素にそれぞれ入れていく形でした。すいませんでした。

お礼日時：2007/04/19 21:50

No.1 回答者： SAKENOSAKA 回答日時： 2007/04/19 02:27

ややこしいアレですな。

意味を理解するのに時間かかりました。

調べたい数字を引数にして
戻り値は前にいくつ数字があるか返す front(int a)
戻り値は後ろにいくつ数字があるか返す after(int a)

というメソッドをそれぞれ実装すればいけるのでは？

変数内が
123456789
だとして,問題が7だとしたら
front(7) //6が返る
after(7) //2が返る　
ように

各要素について検査し
front()+after()がルールに当てはまる場合
のみヒットとするようにしたらいけるのでは？

この回答への補足

回答ありがとうございます。なかなか意味を伝えることが出来ずすいませんでした。
このルールは、Langford's Problem（ラングフォードの問題）なのかなと思いましたが分かりません。

私のプログラミングは初心者に近い部類ですのでより簡単な方法で解決したいと思っています。
SAKENOSAKAさんのに指摘された方法はルールを確かめるということで良いでしょうか？それと、私のプログラムに実装するという形でしょうか？
何分初心者ですので、より具体的な解法のご教授をお願いします。

補足日時：2007/04/19 14:56