ポストの対応問題

非可解問題にポストの対応問題というのがあって。
ポストの対応問題とは、

インスタンス：列の有限集合　{(x_1,y_1),(x_2,y_2)...(x_k,y_k)}

があって、x_i1x_i2...x_in=y_i1y_i2...y_in であるような正数列i_1i_2...i_nが存在するかどうか調べる問題です。　

具体例として　
　　　　　{(1,111),(10111,10),(10,0)}
つまりx_1=1,y_1=111,x_2=10111,y_2=10,x_3=10,y_3=0
であり,このとき2113とインスタンスを並べたとき、
x_2x_1x_1x_3=101111110
y_2y_1y_1y_3=101111110
となって同じ数列になる。その他の組み合わせを調べるのに力ずくで見つけるのは、限界があるので、このポストの
対応問題のプログラムは作るろうと思ったのですがプログラム歴が浅いのでまったく歯が立ちませんでした、C言語でどのようにプログラムを作ったらよいでしょうか？

プログラム形として、解の上限数を決めて、x_1=1,y=111,
x_2=10111,y_2=10,x_3=10,y_3=0と入力して、
結果として X=101111110,Y=101111110、解2113、2113の繰り返しを除いたその他のXとYの数列が同じの値と解が出てくるようなプログラムです、質問が分かりにくいとは思いますが、よろしくおねがいします。

No.2 ベストアンサー 回答者： JaritenCat 回答日時： 2004/11/13 20:08

文字列の比較は、xとyの文字をそれぞれstrncatで連結したあとでstrncmpすればいいかと。

サンプル（問題固定、重複解削除なし）です。
文字数を計算しておくとか、解にならない組み合わせを排除しておくなどの工夫をしてないので遅いです。
#include <stdio.h>
#include <string.h>

#define N 20 /* 解の最大長 */
#define M 3　/* 要素数 */
char xstr[M][10]={"1","100","11"};
char ystr[M][10]={"11","0","0"};
int retsu[N];
/* 解(長さnum)の文字列結合＆比較 */
void check(int num) {
　int i;
　char xbuf[N*10]="", ybuf[N*10]="";
　for (i=0; i<num; i++) {
　　strncat(xbuf,xstr[retsu[i]],10);
　　strncat(ybuf,ystr[retsu[i]],10);
　}
　if (strncmp(xbuf,ybuf,N*10)==0) {
　　/* 表示 */
　　printf("X=%s\n",xbuf);
　　printf("Y=%s\n",ybuf);
　　printf("解:");
　　for (i=0; i<num; i++) {
　　　printf("%d",retsu[i]+1);
　　}
　　printf("\n\n");
　}
}
/* maxの長さの組合せを作ってretsuに入れる(再帰) */
void kumi(int num, int max) {
　int i;
　if (num==max) {
　　check(num);
　} else {
　　for (i=0; i<M; i++) {
　　　retsu[num]=i;
　　　kumi(num+1, max);
　　}
　}
}
/* メイン */
int main(void) {
　int i;
　for (i=1; i<=N; i++) {
　　printf("長さ=%d\n",i);
　　kumi(0, i);
　}
　return 0;
}

この回答へのお礼

役に立つプログラム本当にありがとうございました。
早く処理できるようにプログラムがんばって工夫してみます。

お礼日時：2004/11/14 21:31

No.1 回答者： JaritenCat 回答日時： 2004/11/13 07:36

単純に、組み合わせを作る→同じか調べるの繰り返しになると思います。

・組み合わせは、1個の場合(1,2,3)、2個の場合(11,12,13,21,22,23,31,32,33)、3個の場合(111,112,113,121,122,123・・・)と好きなだけ増やしていけばいいですよね。
・同じかどうか調べるのは、xとyを文字列の配列にしておいて、組み合わせの通りつないで、文字列比較するとか。
・重複解の除去は、見つけた解を保存しておいて、新しく見つけた解と今までの解を(前方一致で)比較すればいいような。

とりあえずできてるとこだけでもプログラムを見せてもらえたらコメントできると思いますが。

この回答への補足

回答ありがとうございます。
考えたプログラムです、配列の比較が分からなかったので
すごく短いプログラムになってます。


#include<stdio.h>
#include<string.h>

main()
{
char x1[10],x2[10],x3[10];
char y1[10],y2[10],y3[10];
char X[100],Y[100];
int m1,m2,m3,n1,n2,n3;

　/*0か1の値を代入する。*/

scanf("%s",x1); /* x1,y1で1つの要素 */
scanf("%s",y1);
scanf("%s",x2);　/*　x2,y2で1つの要素 */
scanf("%s",y2);
scanf("%s",x3); /* x3,y3で1つの要素 */
scanf("%s",y3);

m1=strlen(x1);
n1=strlen(y1);
m2=strlen(x2);
n2=strlen(y2);
m3=strlen(x3);
n3=strlen(y3);


}
　　
作りたいプログラムは、

x1=1 x2=100 x3=11
y1=11 y2=0 y3=0

と入力したとき、

X=11111100
Y=11111100
解:11132

X=11001111
Y=11001111
解:12311
:
:　
と表示してくれるプログラムです。x1,y1を要素1、x2,y2を要素2、x3,y3を要素3として解で表示される1,2,3は、この要素1,2,3です。

配列x1,y1...x3,y3はそれぞれ長さが異なるので、strncmpなど文字列の比較が上手くできません。

http://www.is.titech.ac.jp/~watanabe/csbook/erra …

このホームページにポストの対応問題についての簡単な説明があります。よろしくお願いします。

補足日時：2004/11/13 15:03