順列、組合せの番号付けと復元

 投稿者:山中和義  投稿日:2009年10月23日(金)15時25分41秒
  パズルの解法で、局面をコード化するためにつくってみました。
ハッシュ関数のサブルーチンです。

参考
 フォルダ SAMPLE 内 PERMUTAT.BAS、COMBINAT.BAS


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

LET N=4 !1~Nまでの数字を使う
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 !1~N
   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 !1~Nまでの数字を使う
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)を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を1とする
      LET m=m-1
      LET v=v-t
   END IF
NEXT i
END SUB
 

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

 投稿者:山中和義  投稿日:2009年11月10日(火)09時11分43秒
  > No.675[元記事へ]

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

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) !0は番人
!!!DO WHILE i>0 AND A(i)<=A(i+1) !0は番人 ※前の順列 ←←←←←
   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
2箇所修正することで、1つ前の順列を生成することもできます。
 

戻る