線の重なり判定、組み合わせ算出プログラム

質問

一直線上に並んだ線の複数のセットが重ならない様に計算する効率的なアルゴリズムは
ありませんか。できればC言語のサンプルや、アルゴリズム名があれば幸いです。

例）
パターンA　-- -- -- --
パターンB - - - - -
パターンC - - -

線では分かりにくいので、アルファベットに変えます。
パターンA　AA■■■AA■■■AA■■■AA
パターンB B■■■■B■■■■B■■■■B
パターンC C■■■■■■■C■■■■■■■C

※■＝空白

ABCを重ならない様にマージ
（マージ過程・ずらしながら確認）
AA■■■AA■■■AA■■■AA
■■■B■■■■B■■■■B■■■■B
■■■■■■C■■■■■■■C■■■■■■■C

●結果例　１つのパターン例
AA■B■■CAA■B■■AA■BC■AA■B■■■C

回答No.1

sygh · ベストアンサー

64bit整数を使って比較処理を簡素化していますが、
アルゴリズム的には特に何も工夫していない、総当たりのコードです。
各パターンセットの最大長は64個までとなっています。

Visual C++ 2010でのみテスト済み。
すべての組み合わせを確認する場合は出力をファイルにリダイレクトしてください。

#include <stdio.h>
#include <conio.h>

void PrintBin64Inv(unsigned long long v)
{
int i;
for (i = 0; i < 64; i++)
{
putchar(v & (1LL << i) ? '1' : '0');
}
putchar('\n');
}

void main()
{
// 最下位ビットを左端に、最上位ビットを右端に逆表示する。
const unsigned long long ptnA = 0x18c63, ptnB = 0x8421, ptnC = 0x10101;
int shb = 0, shc = 0;
printf("PatternA = ");
PrintBin64Inv(ptnA);
printf("PatternB = ");
PrintBin64Inv(ptnB);
printf("PatternC = ");
PrintBin64Inv(ptnC);
for (shb = 0; shb < 32; shb++)
{
if ((ptnA & (ptnB << shb)) == 0)
{
for (shc = 0; shc < 32; shc++)
{
if (((ptnA | (ptnB << shb)) & (ptnC << shc)) == 0)
{
printf("ShiftAmountB = %d, ShiftAmountC = %d\n", shb, shc);
printf("PatternA = ");
PrintBin64Inv(ptnA);
printf("PatternB2 = ");
PrintBin64Inv(ptnB << shb);
printf("PatternC2 = ");
PrintBin64Inv(ptnC << shc);
continue;
}
}
}
}

puts("Press any key to exit...");
_getch();
}

お礼

回答ありがとうございます。
やはり総当りで見ていくしかないですかね。
ご提示のプログラムの通り、ビットで判定していく方法が簡単そうですので、参考にさせていただきます。
さらに、総当りで考えると、順列的にABC,ACB、BAC，BCA,CAB,CBAもありますので、全パターンを確認して、最適解を出す様にしたいと思います。
ありがとうございました。

回答No.2

yama5140

＞一直線上に並んだ線の複数のセットが重ならない様に計算する・・

　難解だなぁ・・。

＞パターンA　AA■■■AA■■■AA■■■AA
＞パターンB B■■■■B■■■■B■■■■B
＞パターンC C■■■■■■■C■■■■■■■C

　■ を半角１文字 / として、

　パターンA AA/// ５文字の繰り返し
　パターンB B//// ５文字の繰り返し
　パターンC C/////// ８文字の繰り返し

５と５と８の最小公倍数４０まで、「重ならない様に計算する」。
違っていたら、ここまで・・残念。
++++++++++++++++++++++++++++++++++++++++++++++++++++++
ボケ防止対策として・・考えてみました（「●結果例」を無視、失礼）。

　・方法：「ずらしながら確認」

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

#define　ALEN　5　// ■が半角２文字の場合８
#define　BLEN　5　// ■が半角２文字の場合９
#define　CLEN　8　// ■が半角２文字の場合１５
#define　K_LEN　(ALEN*CLEN)　// ■が半角２文字の場合(ALEN*BLEN*CLEN)

void　main()
{
　int　i, A, C, iTop;
　char　cStrA[ 16 ] = "AA///";　// 〃　AA//////
　char　cStrB[ 16 ] = "B////";　// 〃　B////////
　char　cStrC[ 16 ] = "C///////";　// 〃　C//////////////
　char　cWrk1[ K_LEN + 1 ] = { '\0' }, cWrk2[ K_LEN + 1 ];

　for( A = 0; A < ALEN; A++ ){　// パターンB の始まりを「ずらしながら確認」

　　if( 'A' == cStrA[ A ] )　continue;

　　iTop = 0;

　　for( i = 0; i < K_LEN; i++ )　cWrk1[ i ] = cStrA[ i % ALEN ];

　　for( i = A; i < K_LEN; i++ ){

　　　if( '/' == cWrk1[ i ] )　cWrk1[ i ] = cStrB[ ( i - A ) % BLEN ];

　　　else{　// 重なり判定

　　　　if( 'B' == cStrB[ ( i - A ) % BLEN ] ){

　　　　　iTop = i;　// A, B 重なった場所

　　　　　cWrk1[ i ] = '*';

　　　　　break;
　　　　}
　　　}
　　}
　　if( iTop )　cWrk1[ iTop + 1 ] = '\0';

　　printf( "A+B %d %3d %s\n", A, iTop, cWrk1 );

　　for( i = 0; i < ALEN; i++ ){　// パターンC の始まりを「ずらしながら確認」

　　　if( '/' != cWrk1[ i ] )　continue;

　　　strcpy( cWrk2, cWrk1 );

　　　iTop = 0;

　　　for( C = i; C < K_LEN; C++ ){

　　　　if( '/' == cWrk2[ C ] )　cWrk2[ C ] = cStrC[ ( C - i ) % CLEN ];

　　　　else{　// ( A or B ), C 重なり判定

　　　　　if( '*' == cWrk2[ C ] )　iTop = C;

　　　　　if( 'C' == cStrC[ ( C - i ) % CLEN ] ){

　　　　　　if( 0 == iTop )　iTop = C;

　　　　　　cWrk2[ C ] = '*';
　　　　　}
　　　　　if( iTop )　break;
　　　　}
　　　}
　　　cWrk2[ iTop + 1 ] = '\0';

　　　printf( "A+B+C %d %3d %s\n", i, iTop, cWrk2 );
　　}
　　printf( "\n" );
　}
}
注：インデントに全角空白を用いています。コピペ後、タブに一括変換して下さい。

お礼

ご回答ありがとうございます。
何か使えそうな幾何アルゴリズムがあればと質問しましたが、ご提示いただいたプログラムを見ていると、やはり単純にずらしながら確認していくしかない気がしてきました。