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

質問

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

tea_sheep

失礼、記述ミスをしてしまいました。

>１番目の要素の左の値
>１番目の要素の右の値
>２番目の要素の左の値
>２番目の要素の左の値
>……

ではなく

１番目の要素の左の値
１番目の要素の右の値
２番目の要素の左の値
２番目の要素の右の値
……

要は、順番に左、右、左、右、…ということです。

回答No.13

tea_sheep

今までは左側の数字を一通り格納し終えてから右側の数字の構築を行っていましたが、
同時に行ってしまえば、総当たりでも N! 通りで済みますね。

まず、左側の数字 {1～N} の並び順を決定 (順列なので N! 通りの並べ方がある)し、
それを 2N の配列(０初期化しておく)の左から順に格納していきますが、
１番目の要素の左の値
１番目の要素の右の値
２番目の要素の左の値
２番目の要素の左の値
……
の順に繰り返すわけです。
ここで、左の値を格納しようとしたときにすでに別の値が入っていた場合には
次の０の位置を探してそこに格納します。
また、右の値を格納しようとしたときに、インデックスが範囲外であるか、
またはすでに別の値が入っていた場合には、その並びは合致しないものと判断し
次の並びの検証に移ります。

ところで、以前示されたリンク先のLangford's Problemのサイトによると、
Nの値は「4の倍数」または「4の倍数より1小さい数」の場合のみ合致する並びが
存在するようなので、N=9では存在しないようですね。

一応私のソースを載せておきます。N!通りの総当たり法なのでもう少し工夫の余地が
あるとは思いますが。
楽をするためSTL(C++のライブラリ)の next_permutation (順列の生成)や find を
使っているので注意。(でもSTLのコンテナは使っていなかったりと中途半端ですが。)
解の数から言っても、計算が終わるのを待っていられるのはせいぜいN=11が限度で
N=12になると延々と終わらず続くことになります。
(N=11でも解をファイルに書き出せばの話で、直接DOS画面に表示させるとそれだけで
相当遅くなるので注意。)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 配列の表示関数
void PrintSequence(int *seq, int seqCount)
{
　for (int i=0; i<seqCount; i++) {
　　cout << seq[i] << ' ';
　}
　cout << endl;
}

int main()
{
　int fig[] = {1,2,3,4,5,6,7,8};
　const int count = sizeof(fig)/sizeof(fig[0]);

　// next_permutation で使用するためあらかじめ昇順ソートしておく
　sort(fig, fig+count);

　// fig[] の順列並び替えをすべての場合について繰り返す
　int totalCount = 0;
　int matchedCount = 0;
　do {
　　int seq[count * 2] = {0};
　　int seqIdxL = 0;
　　bool errorFound = false;

　　// seq[] の左から順に埋めていく(すでに値が入ってるときは次の 0 の位置)
　　for (int figIdx=0; figIdx < count; figIdx++) {
　　　// 現在の値の左側の位置決め (現在位置以降にある 0 の位置を探す)
　　　seqIdxL = distance( seq, find(seq+seqIdxL, seq+count*2, 0) );
　　　seq[seqIdxL] = fig[figIdx];

　　　// 右側位置決め(範囲外かすでに別の値が格納されている場合は飛ばす)
　　　int seqIdxR = seqIdxL + fig[figIdx] + 1;
　　　if (seqIdxR >= count * 2 || seq[seqIdxR] != 0) {
　　　　errorFound = true;
　　　　break;
　　　}
　　　// 右側位置に格納
　　　seq[seqIdxR] = fig[figIdx];
　　}
　　// エラーなく終了(ルールに合致)した場合は表示
　　if (!errorFound) {
　　　PrintSequence(seq, count*2);
　　　matchedCount++;
　　}
　　totalCount++;
　} while (next_permutation(fig, fig+count));

　// 数を表示
　cout << "Total Count : " << totalCount << endl;
　cout << "Matched Count : " << matchedCount << endl;
　return 0;
}

回答No.12

Oh-Orange

★改良版。
・改良版は次の２つの場所を修正します。
　(1)make 関数の
　　編集前⇒buff[ no ] = (char)(i + '1');
　　編集後⇒buff[ no ] = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[ i ];
　(2)shift 関数を下のものにします。また、check2 関数が追加です。

// チェック２
int check2( puzzle_t x[], int max, puzzle_t value )
{
　int i;

　for ( i = 0 ; i < max ; i++ ){
　　if ( x[i] & value ){
　　　return( 1 );
　　}
　}
　return( 0 );
}

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

　for ( i = 0 ; i < max ; i++ ){
　　do {
　　　if ( msb & x[i] ){
　　　　goto Jump;
　　　}
　　　x[i] <<= 1;
　　} while ( check2(&x[i + 1],(max - (i + 1)),x[i]) );

　　return( 1 );
Jump:
　　while ( !(x[i] & (puzzle_t)1) ){
　　　x[i] >>= 1;
　　}
　}
　return( 0 );
}

最後に:
・改良版では少し高速になりましたので、11個まで確認できました。
　下にその実行結果を載せます。
　3つでは、5通り中、2個の解が見つかった。
　4つでは、21通り中、2個の解が見つかった。
　5つでは、103通り中、1個も解はなかった。
　6つでは、643通り中、1個も解はなかった。
　7つでは、4454通り中、52個の解が見つかった。
　8つでは、34102通り中、300個の解が見つかった。
　9つでは、288123通り中、1個も解はなかった。
　10つでは、2641255通り中、1個も解はなかった。
　11つでは、26234319通り中、35584個の解が見つかった。
・アルゴリズムを変えたため、表示される組み合わせ数も変化したようです。
　アルゴリズムをもうちょっと工夫すれば、もっと高速になりそうだ！多分。
・以上。おわり。

お礼

回答ありがとうございます。
たくさん回答ならびにソースまで示して頂き正直驚きました。
ビット・イメージを利用しているところはなるほどと思いました。
総当りで解決するには相当な計算量がいるので、時間が計り知れませんが、この方法は計算量な格段に少なくてすみますね。
実は、私が質問してから、順列を配列に入れ、その配列を別の配列上で操作し、何とか組合せを出力できるものを作りました。
しかし、Oh-Orangeさんのお考えになったアルゴリズムは、数字を並べるという行為をより自然な形で表現されているとお見受けしました。
私のような初心者からするとOh-Orangeさんのプログラミングは高度なものに感じます。それゆえ勉強になるところが多々ありました。
やはり、発想の転換をして、別のアプローチに挑戦することが勉強なのだと感じました。
幾度ものご教授ありがとうございました。

回答No.10

Oh-Orange

★アルゴリズム
・４つの場合はビット・イメージを利用して、
　400004⇒100001
　30003⇒10001
　2002⇒1001
　101⇒101
　と考える。
・上のビット値を OR して 11111111 になる値がルールと合致する『解』です。
　組み合わせは、101、1001、10001、100001 を順番に１ビットずつシフトして求める。
　総当りするよりは、少ない回数で求まります。
・101 は 101、1010、10100、101000、1010000、10100000 の６組
　2002 は 1001、10010、100100、1001000、10010000の５組
　30003 は 10001、100010、1000100、10001000 の４組
　400004 は 100001、1000010、10000100 の３組となり
　組み合わせは、６×５×４×３＝360通り。
・５つの場合は、5000005 のビットイメージ 1000001 が１つ増える。
　組み合わせは、８×７×６×５×４＝6720通り。
・６つの場合は、60000006 のビットイメージ 10000001 が１つ増える。
　組み合わせは、10×９×８×７×６×５＝151200通り。
　となります。
・unsigned long型で処理しているので 32Bit÷2＝16、さらに１つ引くので 1～15 まで
　処理できる。ただし、for 文のネストを１つずつ増やす必要がある。
　ここを工夫すれば for 文をネストしないでも処理できそうです。
・以上。参考に。

回答No.9

Oh-Orange

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

// 定数
#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 );
}

// 表示
void print( unsigned long x[], int max, unsigned long msb )
{
　char buff[ 33 ] = { 0 };
　unsigned long bit;
　int i, no;

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

　for ( i = 0 ; i < max ; i++ ){
　　for ( no = 0, bit = 1 ; msb > bit ; bit <<= 1, no++ ){
　　　if ( x[i] & bit ){
　　　　buff[ no ] = (char)(i + '1');
　　　}
　　}
　}
　printf( "%s", reverse(buff) );
}

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

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

int main( void )
{
　unsigned long msb = 0377 + 1;
　unsigned long ans = 0377;
　unsigned long x[ 4 ];
　unsigned long a[ 4 ] = {
　　005,
　　011,
　　021,
　　041,
　};
　int max = 0;
　int cnt = 0;

　for ( x[3] = a[3] ; msb > x[3] ; x[3] <<=1 ){
　　for ( x[2] = a[2] ; msb > x[2] ; x[2] <<=1 ){
　　　for ( x[1] = a[1] ; msb > x[1] ; x[1] <<=1 ){
　　　　for ( x[0] = a[0] ; msb > x[0] ; x[0] <<=1 ){
　　　　　if ( check(x,4,ans) == OK ){
　　　　　　print( x, 4, msb );
　　　　　　printf( "⇒○\n" );
　　　　　　cnt++;
　　　　　}
　　　　　else{
　　　　　　/*
　　　　　　print( x, 4, msb );
　　　　　　printf( "⇒×\n" );
　　　　　　*/
　　　　　}
　　　　　max++;
　　　　}
　　　}
　　}
　}
　printf( "%d通り中、%d個見つけた。\n", max, cnt );
　return( 0 );
}

回答No.8

tea_sheep

1103yさんが示したリンク先のLangford's Problemを見てみましたが、どうやら
数字の列を前半／後半に分けて考えるというものではないようですね。
「1～Nまでをそれぞれ2個ずつ含み、1と1の間に1個の数、2と2の間に2個の数、…
となるように配置された数字の列」のことのようです。
さらには、今回は2つずつのみですが、それぞれの数字が3つずつ(triplets)や
4つずつ(quadruple)なんてものも存在するようで。

となると、今までルールそのものを誤解していたようなので、別のアプローチが
必要です。
再び総当たりの方法を考えるとすると、

a[18] = {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9};

を並び替え、すべての場合について条件に適合しているか調べることになりますが、
この場合の並び替えのパターンは

(18の階乗)÷(2の9乗)＝約12兆5000万通り

となるので、単純な並べ替えの総当たりはやめておいたほうがよさそう。
代わりに、それぞれの数字の位置インデックス持つ配列を考える方法なども考えられます。
配列posL[]に、各々の「左側にある方の数字」の位置インデックスを持たせるとします。

posL[0]=(左側にある数字1の位置インデックス)
posL[1]=(左側にある数字2の位置インデックス)
…
posL[N-1]=(左側にある数字Nの位置インデックス)

posL[0]～posL[N-1]の値が「0～(2N-1)までの数字からN個取り出す場合の順列の並び」と
なるように格納します。この場合、それぞれについて右側の数字のインデックスを

(右側インデックス)=(左側インデックス)+(要素の値)+1

で求めてposR[]に代入します。

posR[0]=posL[0]+1+1
posR[1]=posL[1]+2+1
…
posR[N-1]=posL[N-1]+N+1

この場合も、右側インデックスposR[]の構築中に、それまでに確定している要素との
衝突がないかどうかの判定をしていくことになります。
ただし、この方法でも、単純な総当たりで行っていく場合には、posL[]の並び替えで

(18の階乗)÷(9の階乗)＝176億通り

のパターンがあるので、もっとパターンを絞り込む工夫が必要です。

この問題の解法については、リンク先からたどれるWebページや
関連する論文など参照してみたほうがよさそうです(英語ばかりのようですが)。

お礼

度重なるご回答ありがとうございます。
posL[]　と　posR[]　をそれぞれ用意し、組み合わせるということでしょうか。

あと、Ｃ言語ではなく、perl言語ですが、このアルゴリズムを別の方法で実現させている方のサイトを見つけました。
http://www12.ocn.ne.jp/~kumo/kazunosa.html

しかし、これは別の方法で、且つperlはよく分かりませんので参考です。

回答No.7

tea_sheep

もしかして、N=4以上の場合は「ルールを満たす並びは存在しない」だったりしませんかね。

N=4～10の場合について前半部分の順列の並び総当たりで調べてみても見つからないし、
N=4での24通りの並びについて、実際に全部書き出してみてもルールに該当しそうな
ものが見つからないんですが。

補足

回答ありがとうございます。
考えてみましたが、確かにそうかもしれません。
私の考えが間違っていたかもしれません。
と言うのは、tea_sheepさんのおっしゃるように、全ての順列を前半部分に列挙しても、３までしか順列には合致しないのかも知れません。
とすると、n=4の場合
23421314　と反転の　41312432
の２つを見つけ出すプログラムにしなければならないかもしれません。
http://www.wschnei.de/digit-related-numbers/langfords-problem.html

http://mathworld.wolfram.com/LangfordsProblem.html
上のリンクはラングフォードの問題というものです。
但し、出題者には今まで考えてきた順列からチェックするというやり方を示されたような気がするのですが・・・
もしもソースをお考えでしたら参考までに拝見させて頂けるとありがたいです。
お手数お掛けしてすいません。

回答No.6

tea_sheep

今回の問題の場合、前半部分の並びを決めると、後半部分については
ルールに合致する並びが「存在しない」か「1通りだけ存在する」かの
どちらかとなります。
そこで、それぞれの前半部分の並びについて、ルールに合致する後半部分が
存在するものと仮定して、前半部分の並びを元に、後半部分の並びを各要素
ごとに順に構築していきます。
その構築の途中で、何らかの矛盾（後半部分の配列インデックスが範囲外に
なったていたり、すでに別の要素がその位置に入っている）が生じた場合には
「存在しない」方だったと判断して、次の並びの検証に移ります。

手順としては1～3の場合、
(1)後半をゼロ埋めしておく
　a[] = {3, 1, 2, 0, 0, 0};

(2)最初の要素(a[0]=3)の、後半部分におけるインデックスを決定
　(後半インデックス)=(前半インデックス)+(要素の値)+1
なので、a[0]の後半でのインデックスは 0+3+1=4

(3)インデックスが後半部分の範囲内にあることを確認
　この場合は 3～5 であること。4なので問題なし。

(4)後半インデックスの位置にすでに他の値が格納されていない(0である)ことを
　確認して、値を格納する。
　最初の要素なので問題なし
　{3, 1, 2, 0, 3, 0} ← a[4]=3

(5)次の要素(a[1]=1)について (2)～(4) を実行
　後半インデックス=1+1+1=3
　{3, 1, 2, 1, 3, 0} ← a[3]=1

(6)最後の要素(a[2]=2) について (2)～(4) を実行
　後半インデックス=2+2+1=5
　{3, 1, 2, 1, 3, 2} ← a[5]=2

で完了。上記の(2)～(4)を前半部分の各要素について繰り返せばよいです。
上記例では(3),(4)のチェックで引っかかることなく後半部分を構築できたので
この並びがルールを満たしていることになります。

他の例として、{1,3,2,0,0,0}から開始すると、最初の要素 a[0]=1 に対する
後半部インデックスの範囲チェック(2)に引っかかるので、この並びは×。

別の例では、{3,2,1,0,0,0}だと、2つ目の要素 a[1]=2 の(4)のチェックにおいて
すでに別の値(a[0)が格納先(a[4])に入っているため、この並びも×。

お礼

再びのご回答ありがとうございます。

tea_sheepさんご指摘のように、（３）＆（４）のチェックが重要になりますね。
特に、後半部は０に初期化されているので、（４）の時に、０がある場合にのみ値を代入するということですね。

回答No.5

tea_sheep

よくよく考えたら、わざわざ後半部分の並びを作り出さなくても、
前半部分の各要素の値と位置からルールにマッチしているかどうかの
判定が可能でしたね。
それぞれの要素について、値と位置から後半部分における位置を計算し、
それが他の要素のものと重なっていなければOKという形で。
それなら、9!＝約36万通りについて調べればいいので、まあ総当たりでも
何とかならないこともないですが。

お礼

回答ありがとうございます。
なるほど、あまり計算量を考えずやっていました。
前半部分からマッチしているかどうか判定するということですね
私も質問時から考えて来ましたが、前半部から一つずつルールに当てはめて、後半部分においていくというものを作りました。
やはり、ルールにあっているかどうかの判定が良く分かりません。
今考えているのは、例えばn＝３の時

312132　を作ったとして、前半部 a[0] の値（３）が
後半部a[3] a[4]a[5]のどれかに入っていたとき、カウンタを設けて、カウンタに＋１足す。
同様にa[1] a[2]についても後半部と比較します。
すると３つの数字が全部見つかった場合は、カウンタは３になります。
n=3なので、n==カウンタ　となればルールと完全一致となり、出力するというものを作りましたが・・・３の場合は出来ますが４からがうまく行きませんでした。

回答No.4

tea_sheep

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

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