ポストの対応問題
非可解問題にポストの対応問題というのがあって。
ポストの対応問題とは、
インスタンス：列の有限集合 {(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の数列が同じの値と解が出てくるようなプログラムです、質問が分かりにくいとは思いますが、よろしくおねがいします。
