十進BASIC 第2掲示板 過去ログ

!参考サイト　http://www.research.att.com/~njas/sequences/A000186
!n=0,1,2,3, 4,  5,    6,      7,…
!  1,0,0,2,24,552,21280,1073760,…


!かくらん（攪乱）順列（完全順列、乱列）の数、モンモール数（Montmort number）
!参考サイト　#1201

!●場合の数　d[n]

LET N=4 !ｎ個の並び

LET dn=Derangements(N)
PRINT "場合の数="; dn

DIM B(dn,N) !並びを記録する


!●並びの列挙

DIM A(N)

LET c=0

LET i=0 !順列０～(FACT(N)-1)通りの中から
DO WHILE i<=FACT(N)-1
   CALL Num2PermFactorial(i, A,N) !番号から順列を生成する

   FOR k=1 TO N !変化しない要素を除く
      IF A(k)=k THEN EXIT FOR
   NEXT k
   IF k>N THEN !該当するなら
      LET c=c+1

      !!!MAT PRINT A; !debug
      FOR x=1 TO N !copy it
         LET B(c,x)=A(x)
      NEXT x

      LET i=i+1
   ELSE
      LET i=i+FACT(N-k) !スキップする
   END IF
LOOP

PRINT "場合の数="; c


!●直積で、その組合せを検証する

LET c=0

FOR i=1 TO dn-1 !組合せ、後で２倍する
   FOR j=i+1 TO dn
      FOR x=1 TO N !同じ位置の数字が同じかどうか確認する
         IF B(i,x)=B(j,x) THEN EXIT FOR
      NEXT x
      IF x>N THEN !すべて異なるなら
         LET c=c+1

         !PRINT "No.";c
         !FOR x=1 TO N
         !   PRINT B(i,x);
         !NEXT x
         !PRINT
         !FOR x=1 TO N
         !   PRINT B(j,x);
         !NEXT x
         !PRINT
         !PRINT
      END IF
   NEXT j
NEXT i
PRINT "場合の数="; 2*c


END


EXTERNAL FUNCTION Derangements(n) !かくらん（攪乱）順列（完全順列、乱列）の数
LET t=0
FOR k=0 TO n
   LET t=t+FACT(n)*(-1)^k/FACT(k) !FACT(n)*Σ{(-1)^k/FACT(k)}
NEXT k
LET Derangements=t
END FUNCTION

EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する　※辞書式順序
LET v=h !非負の10進数整数を階乗進数へ
FOR j=N TO 1 STEP -1 !下の桁から順に
   LET w=N-j+1
   LET t=INT(v/w)
   LET A(j)=v-t*w +1 !階乗進数の各桁の値＋１　A[1..N]=(N-1)! … 3! 2! 1! 0!
   LET v=t
NEXT j
FOR j=N-1 TO 1 STEP -1 !順列パターンへ
   FOR k=j+1 TO N
      IF A(k)>=A(j) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB