covering designのt=2に相当、
La Jolla Covering Repository Tablesに全部載ってます…
リンク先クリックすればいいんだね。
Combinatorial covering designs に文献とかあるから、なんかもう・・・
もういいや
fortran90によるのコードはこのページの下の方です
だんだんと条件を付け加えて更新していくつもりです。n=9~10でm=3,4程度は厳しいです。
力技でやってみたよ!
主眼が回数になっているので、実際の組み合わせは？と気になってやったものです。
事の発端
あのね。前々からずーーっと答えが知りたい数学の問題があって。
①n人のグループがいる
②プリクラ機には一度にm人しか入れない
メンバーがほかの各メンバーと一度は同じ写真におさまるためには最低何回撮影する必要があるか？ ※ちなみに(n,m)=(7,5)の時は3
#プリクラ問題
— あしやまひろこ (@hiroko_TB) 2015, 1月 1
コンピュータによる総当たりでは今のままではn=10位が限界です。
だんだんと改良して増やせていければ、と。
コードは後ほど僕に時間ができ次第、公開します。
#プリクラ問題 もすっかり大人しくなりましたが、懲りずに表（n≦"99", m≦25）をアップします。現人神ジョージ先生の解答を待ちましょう。 pic.twitter.com/5q3p1seCUa
— リッチカスタードソフト (@298itf) 2015, 1月 6
より↓
念のための確認もかねて、計算は表の値-1から確かめて総当たりを行った結果です。なので具体的な組み合わせが載っているものは正しいはずです。
組み合わせの総数はおおよそ
\(\displaystyle \sum_{q=3}^{q^{Answer}} {}_{{}_nC_m}C_{q}\)
という膨大な数の組み合わせとなります。ここで\(q^{Answer}\)はプリクラ問題の最小回数です。
\(q=3\)はあり得ない、全てを検証する必要はない、など確実にわかる要素は多いですが、例えばn=9,m=3,解q=12を考えると
\(\displaystyle {}_{{}_9C_3}C_{12}=112,992,892,764,570 \ \ \sim 10^{14}(=100T)\)回
の計算が必要です。理想的な状況を考え、cpu10GHz,コア数10で並列処理で行う場合、計算時間は
\(\displaystyle \frac{10^{14}回}{10\times 10^{9}Hz\cdot 10\mbox{コア}}=1000[秒]\)
なのでぎりぎり計算できそうかなーくらいになります。
しかし、このあたりが限界で、n=10,m=3,解q=17になると、
\(\displaystyle {}_{{}_{10}C_3}C_{17}=189,916,591,435,396,829,640\ \ \sim 10^{20}(100E)\)回
の計算となります。先ほどの設定で行うならば、\(10^{9}\)秒~31.7年かかります。
スパコンの京(10PHz)をフルに使えるならば1000[s]で終わります。しかしそこで終わりです。n=11は…もう無理です。
効率のいい方法を考えない限り、解は得られません。
| n\m | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 6 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 10 | 4 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 6 | 15 | 6 | 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 |
| 7 | 21 | 7 | 5 | 3 | 3 | 1 | 1 | 1 | 1 | 1 |
| 8 | 28 | 11 | 6 | 4 | 3 | 3 | 1 | 1 | 1 | 1 |
| 9 | 36 | 12 | 8 | 5 | 3 | 3 | 3 | 1 | 1 | 1 |
| 10 | 45 | 17 | 9 | 6 | 4 | 3 | 3 | 3 | 1 | 1 |
| 11 | 55 | 19 | 11 | 7 | 6 | 4 | 3 | 3 | 3 | 1 |
(3,2)=3
1 2
1 3
2 3
(4,2)=6
略
(4,3)=3
1 2 3
1 2 4
1 3 4
(5,2)=10
略
(5,3)=4
1 2 3
1 2 4
1 2 5
3 4 5
(5,4)=3
1 2 3 4
1 2 3 5
1 2 4 5
(6,2)=15
略
(6,3)=6
1 2 3
1 2 4
1 5 6
2 5 6
3 4 5
3 4 6
(6,4)=3
1 2 3 4
1 2 5 6
3 4 5 6
(6,5)=3
1 2 3 4 5
1 2 3 4 6
1 2 3 5 6
(7,2)=21
略
(7,3)=7
1 2 3
1 4 5
1 6 7
2 4 6
2 5 7
3 4 7
3 5 6
(7,4)=5
1 2 3 4
1 2 3 5
1 2 3 6
1 2 3 7
4 5 6 7
or
1 2 3 5
1 4 6 7
2 3 4 5
2 4 6 7
3 5 6 7
(7,5)=3
1 2 3 4 5
1 2 3 6 7
1 4 5 6 7
(7,6)=3
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
(8,2)=28
略
(8,3)=11
計算中…
(8,4)=6
1 2 3 4
1 2 5 6
1 2 7 8
3 4 5 6
3 4 7 8
5 6 7 8
(8,5)=4
1 2 3 4 5
1 2 3 4 6
1 2 3 7 8
4 5 6 7 8
(8,6)=3
1 2 3 4 5 6
1 2 3 4 7 8
1 2 5 6 7 8
(8,7)=3
1 2 3 4 5 6 7
1 2 3 4 5 6 8
1 2 3 4 5 7 8
(9,2)=36
略
(9,3)=12
計算中…
(9,4)=8
1 2 3 5
1 2 3 6
1 2 4 7
1 2 8 9
1 3 4 8
1 3 7 9
4 5 6 9
5 6 7 8
info)cputime=3.0415[s], Nc=10523209, com=1 2 35 115 126
(9,5)=5
1 2 3 4 5
1 2 3 4 6
1 2 7 8 9
3 4 7 8 9
5 6 7 8 9
(9,6)=3
1 2 3 4 5 6
1 2 3 7 8 9
4 5 6 7 8 9
(9,7)=3
1 2 3 4 5 6 7
1 2 3 4 5 8 9
1 2 3 6 7 8 9
(9,8)=3
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 9
1 2 3 4 5 6 8 9
(10,2)=45
略
(10,3)=17
計算厳しい
(10,4)=9
計算中(4日後くらい?)
(10,5)=6
(10,6)=4
1 2 3 4 5 6
1 2 3 4 7 8
1 2 3 4 9 10
5 6 7 8 9 10
(10,7)=3
1 2 3 4 5 6 7
1 2 3 4 8 9 10
1 5 6 7 8 9 10
(10,8)=3
1 2 3 4 5 6 7 8
1 2 3 4 5 6 9 10
1 2 3 4 7 8 9 10
(10,9)=3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 9 10
(11,2)=55
略
(11,3)=19
(11,4)=11
(11,5)=7
(11,6)=
(11,7)=4
1 2 3 4 5 6 7
1 2 3 4 5 6 8
1 2 3 4 9 10 11
5 6 7 8 9 10 11
(11,8)=3
1 2 3 4 5 6 7 8
1 2 3 4 5 9 10 11
1 2 6 7 8 9 10 11
(11,9)=3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 10 11
1 2 3 4 5 8 9 10 11
(11,10)=3
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 11
1 2 3 4 5 6 7 8 10 11
fortran90のコード。総当たりで調べます。
別にinputファイルが必要です。n:m=3:2以上の時は考慮していません。3回で終わるからね。
下の例はn=6, m=3に相当しています。(inputのrはmに相当します。)
qiは調べ始める最低回数、qeは調べ終わる最高回数です。
出力はこうなります。
q --> 3
q --> 4
q --> 5
q --> 6
q --> 7
number of calculation 1276464
cpu_time 0.905050993 [sec]
+------------+
1 2 3
1 4 5
1 6 7
2 4 6
2 5 7
3 4 7
3 5 6
+------------+
ここからfortran90のコード。gfortranで確かめています。
implicit none
integer::n,r,qi,qe,qc
integer::i,j
real::t1,t2
integer,allocatable::groups(:,:)
n=7
r=3
qi=3
qe=10
allocate(groups(1:qe,1:r))
groups=0
call cpu_time(t1)
call pkprob(n,r,qi,qe,qc,groups)
call cpu_time(t2)
write(6,*)"cpu_time",t2-t1,"[sec]"
write(6,'(A)')"+------------+"
do i=1,qc
do j=1,r
write(6,'(i3)',advance='no')groups(i,j)
enddo
write(6,*)
enddo
write(6,'(A)')"+------------+"
stop
end program main
!==========================
subroutine pkprob(n,r,qi,qe,qc,groups)
!Covering Design t=2
implicit none
integer,intent(in)::n,r,qi,qe
integer,intent(out)::qc,groups(1:qe,1:r)
integer::q,M,ic,ncalc
integer::i,j,q2,k
integer,allocatable::ini(:),tmp(:),cgroup(:,:),pk(:,:)
integer,allocatable::choose(:)
integer::check1,nCr
integer::csign
! logical::csign,gsign
external::nCr
!Combination M=nCr
M=nCr(n,r)
write(6,*)"M",M
!csign : Sign of critical combination of array
!ic : Critical value of i which number of combination of combination
!qc : Critical value of q which number of combination of combination
!pk(1:n,1:n): Checking array if every number fill(1) combination or not(0)
!ncount(1:n): To check calculation number of times
allocate(ini(1:r),tmp(1:r),cgroup(1:M,1:r))
ini(1:r)=0
cgroup(1:M,1:r)=0
tmp(1:r)=0
do j=1,r
ini(j)=j
tmp(j)=ini(j)
enddo
!Substitute combination to cgroup.
do i=1,M
cgroup(i,1:r)=tmp(1:r)
call combination(n,r,ini,tmp)
enddo
deallocate(ini,tmp)
!csign : Sign of critical combination of array
!ic : Critical value of i which number of combination of combination
!qc : Critical value of q which number of combination of combination
!pk(1:n,1:n): Checking array if every number fill(1) combination or not(0)
!ncount(1:n): To check calculation number of times
csign=0
ic=0
qc=0
allocate(pk(1:n,1:n))
pk=0
ncalc=0
!q : We need to consider below combination.
! Example ) n=5, r=3 case.
!
!cgroup(i,1:r)
!i\r| 1 2 3
!----------
! 1 | 1 2 3
! 2 | 1 2 4
! 3 | 1 2 5
! 4 | 1 3 4
! 5 | 1 3 5
! 6 | 1 4 5
! 7 | 2 3 4
! 8 | 2 3 5
! 9 | 2 4 5
!10 | 3 4 5
!
!We have to choose q= 3 or 4 or 5 ...combination of "cgroup".
!Sum total of these combination can write D=_{nCr}C_q.
!Specifically,
!---choose q groups from cgroup
! +----q=3----+ +-----q=4-----+ +------q=5------+
! |choose(1:q)| | choose(1:q) | | choose(1:q) |
! | l | | | l | | | l | |
! |===|=======| |===|=========| |===|===========|
! | 1 | 1 2 3 | | 1 | 1 2 3 4 | | 1 | 1 2 3 4 5 |
! | 2 | 1 2 4 | | 2 | 1 2 3 5 | | 2 | 1 2 3 4 6 |
! | 3 | 1 2 5 | | 3 | 1 2 3 6 | | 3 | 1 2 3 4 7 |
! | 4 | 1 2 6 | | 4 | 1 2 4 7 | | 4 | 1 2 3 4 8 |
! | 5 | 1 2 7 | | 5 | 1 2 4 8 | | 5 | 1 2 3 4 9 |
! | 6 | 1 2 8 | | 6 | 1 2 5 9 | | 6 | 1 2 3 4 10|
! | 7 | 1 2 9 | | 7 | 1 2 5 10| | 7 | 1 2 3 5 6 |
! |...| . . . | |...| . . . . | |...| . . . . |
! |120| 4 5 6 | |210| 7 8 9 10| |252| 6 7 8 9 10|
! +-----------+ +-------------+ +---------------+
!
! If q=4, l=3
! We choose below combination, and check satisfy condition or not by "pk".
! 1 | 1 2 3
! 2 | 1 2 4
! 3 | 1 2 5
! 6 | 1 4 5
do q=qi,qe
write(6,'(A,i5)')"q -->",q
allocate(choose(1:q),ini(1:q))
choose(1:q)=0
ini(1:q)=0
do j=1,q
ini(j)=j
choose(j)=ini(j)
enddo
csign=0
do while(csign.eq.0)
!condition 1 to reduce calculation
check1=cgroup(choose(1),1)
if(check1.ne.1)exit
!condition 2 to reduce calculation
check1=cgroup(choose(2),1)
if(check1.ge.2)exit
!condition 3 to reduce calculation for less than n:r=3:2
check1=cgroup(choose(q),1)
if(check1.ge.3)then
pk=0
do q2=1,q
do j=1,r
do k=1,r
pk(cgroup(choose(q2),j),cgroup(choose(q2),k))=1
enddo
enddo
enddo
!memory calculation number of times
ncalc=ncalc+1
if(minval(pk).eq.1)then
csign=1
qc=q
endif
if(csign.eq.1)exit
endif
!go forward choose(1:q)
call combination(M,q,ini,choose)
enddo
if(csign.eq.1)exit
deallocate(choose,ini)
enddo
write(6,*)"number of calculation",ncalc
groups(1:qe,1:r)=0
do i=1,qc
do j=1,r
groups(i,j)=cgroup(choose(i),j)
enddo
enddo
return
end subroutine pkprob
!---------------------------------
subroutine combination(n,r,ini,arr)
implicit none
integer(8)::i,n,r,ini(1:r),bef(1:r),arr(1:r)
integer(8)::numx
logical::key(1:r)
bef(1:r)=arr(1:r)-ini(1:r)
arr(1:r)=0
key(1:r)=.false.
numx=n-r
do i=1,r
if(bef(i).eq.numx)key(i)=.true.
enddo
do i=1,r-1
if(key(i+1))then
if(key(i))then
if(i.ne.1)arr(i)=arr(i-1)
else
arr(i)=bef(i)+1
endif
else
arr(i)=bef(i)
endif
enddo
if(key(r))then
arr(r)=arr(r-1)
else
arr(r)=bef(r)+1
endif
arr(1:r)=arr(1:r)+ini(1:r)
return
end subroutine combination
!----------------------------------
function nCr(n,r)
implicit none
integer(8)::n,r,i,r0,nCr
r0=n-r
if(r.le.r0)r0=r
nCr=1
do i=1,r0
nCr=nCr*(n-r0+i)
nCr=nCr/i
enddo
return
end function nCr
