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

!順列 perm(n,r) 通りのパターンに、0 ～ perm(n,r)-1 の番号をつける方法

LET N=4 !１～Ｎまでの数字を使う
LET R=4

DATA 1,2,3,4 !順列 PERM(N,N)=FACT(N) のテスト・データ
DATA 1,2,4,3
DATA 1,3,2,4
DATA 1,3,4,2
DATA 1,4,2,3
DATA 1,4,3,2
DATA 2,1,3,4
DATA 2,1,4,3
DATA 2,3,1,4
DATA 2,3,4,1
DATA 2,4,1,3
DATA 2,4,3,1
DATA 3,1,2,4
DATA 3,1,4,2
DATA 3,2,1,4
DATA 3,2,4,1
DATA 3,4,1,2
DATA 3,4,2,1
DATA 4,1,2,3
DATA 4,1,3,2
DATA 4,2,1,3
DATA 4,2,3,1
DATA 4,3,1,2
DATA 4,3,2,1

DIM A(R),B(R)
FOR d=1 TO PERM(N,R) !データを読み込む
   MAT READ A

   LET h=Perm2Num(A,N,R)
   PRINT h !結果を表示する

   CALL Num2Perm(h, B,N,R) !復元する
   MAT PRINT B;
   MAT PRINT A; !検算
NEXT d

END


!最小完全ハッシュ関数

EXTERNAL FUNCTION Perm2Num(A(),N,R) !順列パターンに番号を付ける　※辞書式順序
LET v=0
FOR j=1 TO R
   LET t=A(j)
   LET v=v+perm(N-j,R-j)*(t-1)
   FOR k=j+1 TO R
      IF A(k)>t THEN LET A(k)=A(k)-1
   NEXT k
NEXT j
LET Perm2Num=v
END FUNCTION

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

!組合せ comb(n,r) 通りのパターンに、0 ～ comb(n,r)-1 の番号をつける方法

LET N=6 !１～Ｎまでの数字を使う
LET R=3

DATA 1,2,3 !組合せ comb(6,3)=20 のテスト・データ
DATA 1,2,4 !※数字は小さい順
DATA 1,2,5
DATA 1,2,6
DATA 1,3,4
DATA 1,3,5
DATA 1,3,6
DATA 1,4,5
DATA 1,4,6
DATA 1,5,6
DATA 2,3,4
DATA 2,3,5
DATA 2,3,6
DATA 2,4,5
DATA 2,4,6
DATA 2,5,6
DATA 3,4,5
DATA 3,4,6
DATA 3,5,6
DATA 4,5,6

DIM A(R),B(R)
FOR d=1 TO comb(N,R) !データを読み込む
   MAT READ A

   LET h=Comb2Num(A,N,R)
   PRINT h !結果を表示する

   CALL Num2Comb(h, B,N,R) !復元する
   MAT PRINT B;
   MAT PRINT A; !検算
NEXT d

END


!最小完全ハッシュ関数

EXTERNAL FUNCTION Comb2Num(A(),N,R) !組合せパターンに番号を付ける　※辞書式順序
LET v=0
FOR i=R TO 1 STEP -1 !組合せをビット位置とする
   LET t=N-A(i)
   LET v=v+COMB(t,R-i+1)
NEXT i
LET Comb2Num=(comb(N,R)-1)-v
END FUNCTION

EXTERNAL SUB Num2Comb(h, A(),N,R) !番号から組合せパターンを生成する　※辞書式順序
LET v=comb(N,R)-h
LET m=R
FOR i=N-1 TO 0 STEP -1 !組合せをビット位置とする
   LET t=COMB(i,m)
   IF v>t THEN
      LET A(R-m+1)=N-i !ビット位置(N-i-1)を１とする
      LET m=m-1
      LET v=v-t
   END IF
NEXT i
END SUB


EXTERNAL FUNCTION Comb2Num2(A(),N,R) !組合せパターンに番号を付ける　※辞書式順序ではない
LET v=0
FOR i=R TO 1 STEP -1
   LET t=A(i)-1 !組合せをビット位置とする
   LET v=v+COMB(t,i)
NEXT i
LET Comb2Num2=v
END FUNCTION

EXTERNAL SUB Num2Comb2(h, A(),N,R) !番号から組合せパターンを生成する　※辞書式順序ではない
LET v=h
LET m=R
FOR i=N-1 TO 0 STEP -1 !組合せをビット位置とする
   LET t=COMB(i,m)
   IF t<=v THEN
      LET A(m)=i+1 !ビット位置iを１とする
      LET m=m-1
      LET v=v-t
   END IF
NEXT i
END SUB

!辞書式順序で次の順列を返す

LET N=4
DIM A(N)
DATA 1,2,3,4
!!!DATA 4,3,2,1 !　※前の順列　←←←←←
MAT READ A
MAT PRINT A;

FOR i=1 TO fact(N)
   CALL NextPerm(A,N,rc)
   PRINT i
   IF rc=0 THEN
      PRINT "ありません。"
      STOP
   END IF
   MAT PRINT A;
NEXT i

END


EXTERNAL SUB NextPerm(A(),N, rc) !辞書式順序で次の順列を返す
LET i=N-1 !順列を右から左にみて、増加列から減少列に変わる位置iを探す
DO WHILE i>0 AND A(i)>=A(i+1) !０は番人
!!!DO WHILE i>0 AND A(i)<=A(i+1) !０は番人　※前の順列　←←←←←
   LET i=i-1
LOOP
IF i=0 THEN !A(1)>A(2)>A(3)> … >A(N)なら　例. N=4、4,3,2,1
   LET rc=0 !完了
   EXIT SUB
END IF

LET j=N !その位置iより右で、A(i)以上で最小の数A(j)を探す
DO WHILE A(i)>=A(j)
!!!DO WHILE A(i)<=A(j) !　※前の順列　←←←←←
   LET j=j-1
LOOP
LET t=A(i) !A(i)とA(j)を交換する
LET A(i)=A(j)
LET A(j)=t

LET i=i+1 !(i+1)からNまでの範囲を逆順にする
LET j=N
DO WHILE i<j
   LET t=A(i) !swap it
   LET A(i)=A(j)
   LET A(j)=t
   LET i=i+1
   LET j=j-1
LOOP
LET rc=1 !未了
END SUB
２箇所修正することで、１つ前の順列を生成することもできます。