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

質問

配列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.11

Oh-Orange · ベストアンサー

★追記。
・調べる組み合わせの数式は『(n*2-2)Ｐ(n)』です。
　４つでは、6P4＝６×５×４×３＝360通り
　５つでは、8P5＝８×７×６×５×４＝6,720通り
　６つでは、10P6＝10×９×８×７×６×５＝151,200通り
　７つでは、12P7＝12×11×10×９×８×７×６＝3,991,680通り
　８つでは、14P8＝14×13×12×11×10×９×８×７＝121,080,960通り
　９つでは、16P9＝16×15×14×13×12×11×10×９×８＝4,151,347,200通り
　※８つまでは計算終了するが、９つは時間がかかりすぎて確認できなかった。

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

// パズル型
typedef unsigned long　puzzle_t;

// 定数
#define OK　1
#define ERR　0
#define SPC　0x20

// 文字列の反転
char *reverse( char buff[] )
{
　char *head = buff;
　char *tail = buff + strlen(buff) - 1;
　char temp[ 1 ];

　while ( head < tail ){
　　temp[ 0 ] = head[ 0 ];
　　head[ 0 ] = tail[ 0 ];
　　tail[ 0 ] = temp[ 0 ];
　　head++;
　　tail--;
　}
　return( buff );
}

// 表示文字列の作成
char *make( char buff[], puzzle_t x[], int max, puzzle_t msb )
{
　int i;

　memset( buff, SPC, BUFSIZ );
　buff[ BUFSIZ - 1 ] = '\0';

　for ( i = 0 ; i < max ; i++ ){
　　int no = 0;

　　do {
　　　if ( x[i] & ((puzzle_t)1 << no) ){
　　　　buff[ no ] = (char)(i + '1');
　　　}
　　} while ( !(msb & ((puzzle_t)1 << no++)) );

　　buff[ no ] = '\0';
　}
　return( reverse(buff) );
}

// チェック
int check( puzzle_t x[], int max, puzzle_t ans )
{
　puzzle_t check = 0;
　int i;

　for ( i = 0 ; i < max ; i++ ){
　　check |= x[ i ];
　}
　return( (check == ans) ? OK : ERR );
}

// シフト
int shift( puzzle_t x[], int max, puzzle_t msb )
{
　int i;

　for ( i = 0 ; i < max ; i++ ){
　　if ( msb & x[i] ){
　　　while ( !(x[i] & (puzzle_t)1) ){
　　　　x[i] >>= 1;
　　　}
　　}
　　else{
　　　x[i] <<= 1;
　　　return( 1 );
　　}
　}
　return( 0 );
}

int main( void )
{
　char buff[ BUFSIZ ];
　puzzle_t x[ 50 ];
　puzzle_t ans;
　puzzle_t msb;
　int max = 0;
　int cnt = 0;
　int i, n;

　do {
　　printf( "3～15を入力して下さい:" );
　　scanf( "%d", &n );
　　printf( "\n" );
　} while ( (n < 3) || (n > 15) );

　ans = ~((~(puzzle_t)0) << (n * 2));
　msb = ((puzzle_t)1 << (n * 2 - 1));

　// ビットイメージの作成
　for ( i = 0 ; i < n ; i++ ){
　　x[ i ] = (((puzzle_t)1 << (i + 2)) | (puzzle_t)1);
　}
　do {
　　if ( check(x,n,ans) == OK ){
　　　printf( "%s⇒○\n", make(buff,x,n,msb) );
　　　cnt++;
　　}
　　else{
//　　　printf( "%s⇒×\n", make(buff,x,n,msb) );
　　}
　　max++;
　} while ( shift(x,n,msb) );

　if ( cnt == 0 ){
　　printf( "%d通り中、1個も解はなかった。\n", max );
　}
　else{
　　printf( "\n%d通り中、%d個の解が見つかった。\n", max, cnt );
　}
　return( 0 );
}

回答No.3

SAKENOSAKA

まだ理解し切れなく申し訳ない。
でもこれはちょっと難しいわ。
色々考えてみたけど一筋縄ではいかんぽい。

(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
と出来ればと思っていたのですが。
色々と考えて頂きありがとうございました。

回答No.2

SAKENOSAKA

ルールに当てはまる場合のみを出力する
ということはだいたいわかるのですが
(前回はこの部分に特化した話です)

それ以前に
２*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[0]=1
p[1]=2
p[2]=3

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

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

補足

再びありがとうございます。
（どういうルールで順列が格納されるべきなのか）
これは、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

回答No.1

SAKENOSAKA

ややこしいアレですな。
意味を理解するのに時間かかりました。

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

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

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

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

補足

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

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