|
|
!カークマン（Kirkman）女学生散歩問題
!n人をk人ずつm個のグループに分けるとする。
LET N=6 !総人数
LET K=2 !グループ内人数
LET M=N/K !グループ数
PRINT N; M
IF M<>INT(M) THEN !整数 ※必要条件
PRINT "解なし"
STOP
END IF
LET D=(N-1)/(K-1) !1を基準にして、k=3なら(1,2,3),(1,4,5),…,(1,n-1,n)のようなグループ分けできるか
PRINT D
IF D<>INT(D) THEN !整数 ※必要条件
PRINT "解なし"
STOP
END IF
LET S=COMB(N-1,K-1) !(1,2),(1,3),…,(1,N)のような(1,…)形の個数
LET T=COMB(N,K) !グループ分けの総数
PRINT S; T
!日程表
! n=6,k=2の場合、m=3
! A(): ┌ m ┐
! ┌ 1 10 15 ← t
! │ 2 * *
! d 3 * *
! │ 4 * *
! └ 5 * *
! ↑ └ s＜x＜t, 10を除く。すなわち、6,7,8,9, 11,12,13,14
! s
!
! ただし、d=(n-1)/(k-1)、s=C(n-1,k-1)、t=C(n,k)、数字1～tは、組合せ番号
DIM F(T) !日程表に埋める「組合せ番号」の使用状況 0:未使用、1:使用中
MAT F=ZER
DIM A(D*M) !日程表 d行m列
DIM Z(K) !「組合せ番号」に対応する「組合せパターン」
LET W=1
FOR i=1 TO T
CALL Num2Comb(i-1, Z,N,K) !一覧を表示する
PRINT STR$(i);": (";
FOR j=1 TO K-1
PRINT STR$(Z(j)); ",";
NEXT j
PRINT STR$(Z(j)); ")"
IF Z(1)=1 THEN !日程表の１列目を埋める
IF K=2 THEN !(1,2),(1,3),(1,4),…,(1,n-1),(1,n)のd個
LET A((W-1)*M+1)=i
LET F(i)=1
LET W=W+1
ELSE
IF MOD(Z(2)-1,K-1)=1 THEN !(1,2,3),(1,3,4),(1,5,6),…,(1,n-1,n)のd個
FOR j=2 TO K-1
IF Z(j)+1<>Z(j+1) THEN EXIT FOR
NEXT j
IF j>K-1 THEN
LET A((W-1)*M+1)=i
LET F(i)=1
LET W=W+1
END IF
END IF
END IF
END IF
IF MOD(Z(1)-1,K)=0 THEN !日程表の１行目を埋める
FOR j=1 TO K-1 !(1,2,3),(3,4,5),(6,7,8),…,(n-2,n-1,n)のm個
IF Z(j)+1<>Z(j+1) THEN EXIT FOR
NEXT j
IF j>K-1 THEN
LET A((Z(1)-1)/K+1)=i
LET F(i)=1
END IF
END IF
NEXT i
MAT PRINT F; !debug
MAT PRINT A; !debug
PUBLIC NUMERIC C !解の数
LET C=0
CALL try(M+2,S,T,D,M,K,A,F) !2行目2列目から順に埋めていく
END
EXTERNAL SUB try(p,S,T,D,M,K,A(),F()) !バックトラック法で検索する
IF p>D*M THEN !すべて埋まったなら
LET C=C+1 !結果を表示する
PRINT "No.";C
!!!MAT PRINT A; !debug
FOR i=1 TO D*M !d行m列
PRINT A(i);
IF MOD(i,M)=0 THEN PRINT
NEXT i
ELSE
IF A(p)=0 THEN !未定義なら
FOR i=S+1 TO T-1 !日程表に埋める「番号」の範囲
IF i>A(p-1) THEN !並びは組合せとする
IF F(i)=0 THEN !未使用なら
LET F(i)=1
LET A(p)=i
LET N=K*M !同じ行で「グループ」を構成する「人」に重複がないか確認する
DIM U(N),Z(K)
MAT U=ZER !全体集合U={1,2,3,…,n}
!!!PRINT INT((p-1)/M)*M+1; p !debug
FOR j=INT((p-1)/M)*M+1 TO p
CALL Num2Comb(A(j)-1, Z,N,K) !※0～COMB(N,K)-1
!!!MAT PRINT Z; !debug
FOR L=1 TO K !部分集合{e1,e2,…,ek}
LET W=Z(L) !要素el
IF U(W)=1 THEN EXIT FOR !既に使用されているなら
LET U(W)=1
NEXT L
IF L<=K THEN EXIT FOR
NEXT j
IF j>p THEN !重複しないなら
CALL try(p+1,S,T,D,M,K,A,F) !次へ
END IF
LET A(p)=0 !元に戻す
LET F(i)=0
END IF
END IF
NEXT i
ELSE !skip it
CALL try(p+1,S,T,D,M,K,A,F)
END IF
END IF
END SUB
EXTERNAL SUB Num2Comb(h, A(),N,R) !番号から組合せパターンを生成する ※辞書式順序
LET v=COMB(N,R)-h
FOR j=R TO 1 STEP -1 !組合せをビット位置とする
FOR i=N-1 TO 0 STEP -1 !組合せをビット位置とする
LET t=COMB(i,j)
IF v>t THEN EXIT FOR
NEXT i
LET v=v-t
LET A(R-j+1)=N-i !ビット位置(N-i-1)を１とする
NEXT j
END SUB
実行結果
6 3
5
5 15
1: (1,2)
2: (1,3)
3: (1,4)
4: (1,5)
5: (1,6)
6: (2,3)
7: (2,4)
8: (2,5)
9: (2,6)
10: (3,4)
11: (3,5)
12: (3,6)
13: (4,5)
14: (4,6)
15: (5,6)
1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
1 10 15 2 0 0 3 0 0 4 0 0 5 0 0
No. 1
1 10 15
2 8 14
3 9 11
4 7 12
5 6 13
No. 2
1 10 15
2 9 13
3 8 12
4 6 14
5 7 11
|
|