|
|
2n枚のカードがある。それぞれに1から2nまでの数字が記入されている。
その半分のn枚のカードをバラバラではなくまとめて抜き出し、
その他のカードの上に重ねる動作を繰り返し、最初の並びの逆順になるまで繰り返す。
たとえば、n=2の場合
抜き出す先頭の位置を2,2,3,2とすると、
1234 2314 3124 2431 4321
￣ ￣ ￣ ￣
最少の回数は4回である。
(2n)回が少なくとも必要である。
抜き出す先頭の位置がn通りなので、n^(2n+α)通りを検証する。
LET N=3 !2n
LET M=2*N
DIM A(M)
FOR i=1 TO M !最初の並び
LET A(i)=i
NEXT i
DIM X(M+1) !位置 ※
CALL try(1,N,A,X)
END
EXTERNAL SUB try(K,N,A(),X())
LET M=2*N
DIM B(M)
FOR i=2 TO N+1 !交換位置を決める
LET X(K)=i
MAT B=A !シャッフル
FOR J=1 TO N
LET B(J)=A(i+J-1)
NEXT J
FOR J=1 TO i-1
LET B(J+N)=A(J)
NEXT J
FOR J=2 TO M !逆に並んだか確認する
IF B(J-1)<B(J) THEN EXIT FOR
NEXT J
IF J>M THEN !結果を表示する
PRINT K
MAT PRINT X;
ELSE
IF K<UBOUND(X) THEN CALL try(K+1,N,B,X) !深さ優先
END IF
LET X(K)=0
NEXT i
END SUB
7
2 3 4 2 3 4 2
7
3 2 4 3 3 2 3
7
3 3 2 3 2 4 3
|
|