マジックへの原理を求めて

 投稿者：GAI  投稿日：2009年11月 1日(日)12時48分46秒
  次々と出題して申し訳ありませんが、次の現象についての調査をお願いします。

１からｎまでの数字が書かれたｎ枚のカードがあり、これを十分にシャッフルする。
トップあるカードを調べその数字だけカードを抜き出し、順番を逆にして元に戻す。
これを繰り返していくと、必ず１がトップに出現する。
これまでにかかる手数が最長になるのは何手かかるかを調べたい。
また、最長手数がかかる初期順列が知りたい。
ｎ枚の場合に分けて（少なくとも１３枚までは）結果が知りたいのでよろしくお願いします。 		 

Re: マジックへの原理を求めて

 投稿者：山中和義  投稿日：2009年11月 1日(日)14時46分51秒
  > No.701[元記事へ]

GAIさんへのお返事です。

１３の階乗は、マシンパワーがいりますが、、、
LET t0=TIME


LET N=9 !枚数

DIM P(N) !１～Ｎまでのカード

LET cmax=0
FOR i=N*fact(N-2) TO fact(N)-1 !順列を生成する　※０～N*(N-2)!-1番目の順列は、1*****、21****
!FOR i=0 TO fact(N)-1 !順列を生成する

   CALL Num2Perm(i, P,N)
   !!!MAT PRINT P; !debug

   LET c=0 !回数
   DO UNTIL P(1)=1 !トップのカードが「１」まで
      CALL reverse(P,(P(1))) !トップのカードの数字だけカードを抜き出し、順番を逆にして元に戻す
      LET c=c+1
   LOOP
   !!!PRINT "回数=";c !debug
   IF c>cmax THEN !最大のものを記録する
      LET cmax=c
      LET i_sav=i
   END IF

NEXT i

PRINT "最大の回数=";cmax
CALL Num2Perm(i_sav, P,N) !順列を再現する
MAT PRINT P;


PRINT "計算時間=";TIME-t0

END


EXTERNAL SUB reverse(A(),N) !１～Ｎまでの並びを逆順にする
FOR i=1 TO INT(N/2) !交換位置は半分まで　※全部すると元に戻る
   swap A(i),A(N-i+1) !中央から対称な位置どうし
NEXT i
END SUB

EXTERNAL SUB Num2Perm(h, A(),N) !番号から順列パターンを生成する　※辞書式順序
LET v=h
FOR j=1 TO N
   LET fac=fact(N-j)
   LET t=INT(v/fac)
   LET A(j)=t+1 !１～Ｎ
   LET v=v-fac*t
NEXT j
FOR j=N-1 TO 1 STEP -1
   FOR k=j+1 TO N
      IF A(j)<=A(k) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB
 

Re: マジックへの原理を求めて

 投稿者：GAI  投稿日：2009年11月 2日(月)06時07分35秒
  > No.702[元記事へ]

山中和義さんへのお返事です。

N=11まで調査しましたが、N=12,13では極端に時間がかかっているようです。
（全パターンを調査しているからなんでしょうね）
調べ物をしていたら、最長手数が判明しました。
そこでこのデータを利用して、その手数がかかる初期順列が知りたいのでプログラムを修正して頂けないでしょうか？
多分時間の節約が可能になると思うんですが。

　　　　　＜最長手数＞
N＝１２・・・・６５回
N＝１３・・・・８０回
N＝１４・・・１０１回
N＝１５・・・１１３回
N＝１６・・・１３９回 		 

Re: マジックへの原理を求めて

 投稿者：山中和義  投稿日：2009年11月 2日(月)08時07分3秒
  > No.703[元記事へ]

GAIさんへのお返事です。

先のプログラムは、すべてのパターンの「開始（乱列）→終了（整列）」を調べています。
これを「終了→開始」に変更しました。
いわゆる幅優先探索で、「どこまで手数が増やせるか（最多手数）」ということです。

本問題では「逆の操作」が可能で、完全整列 1,2,3,4,… から交換を始めます。

これでも１３枚は、、、

ところで、１２枚は６５回ですか？

LET t0=TIME


LET N=13 !１～Ｎのカード

DIM P(N)
FOR i=1 TO N !完全整列 1,2,3,4,…
   LET P(i)=i
NEXT i

LET cmax=0 !最多手数
DIM P_sav(N) !その並び
MAT P_sav=P
CALL try(P,N,0,cmax,P_sav)

PRINT "最大の回数=";cmax
MAT PRINT P_sav;


PRINT "計算時間=";TIME-t0

END


EXTERNAL SUB reverse(A(),N) !１～Ｎ番目までの並びを逆順にする
FOR i=1 TO INT(N/2) !交換位置は半分まで　※全部すると元に戻る
   swap A(i),A(N-i+1) !中央から対称な位置どうし
NEXT i
END SUB

EXTERNAL SUB try(P(),N,c,cmax,P_sav())
DIM W(N)
MAT W=P
FOR i=2 TO N !交換できなくなるまで
   MAT P=W
   IF P(i)=i THEN !i番目のカードが数字iなら交換可能！　※逆の操作
      CALL reverse(P,i) !トップのカードの数字だけカードを抜き出し、順番を逆にして元に戻す
      IF c+1>cmax THEN !最大のものを記録する
         LET cmax=c+1
         MAT P_sav=P
      END IF
      CALL try(P,N,c+1,cmax,P_sav) !次へ
   END IF
NEXT i
END SUB



!WindowsMe、PentiumⅢ700MHz、192MBにて、十進BASIC　２進モードで実行。
!
!最大の回数= 80
! 2  9  4  5  11  12  10  1  8  13  3  6  7
!
!計算時間= 1528.79　　←約25.5分
 

戻る