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

順列

●異なるn個のものをすべて並べる　※{1,2,3,…,n}上の全順列（n-順列）

FACT(N)　場合の数　※組み込み関数
FUNCTION PermFactorial2Num(A(),N)　パターンに番号を付ける
SUB Num2PermFactorial(h, A(),N)　番号からパターンを生成する
SUB PrevPermFactorial(A(),N, rc)　辞書式順序で１つ前を返す
SUB NextPermFactorial(A(),N, rc)　辞書式順序で１つ次を返す


●異なるn個のものから重複を許さずr個を取り出して並べる　※{1,2,3,…,n}上のr-順列

PERM(N,R)　※組み込み関数
FUNCTION Perm2Num(A(),N,R)
SUB Num2Perm(h, A(),N,R)
SUB PrevPerm(A(),N,R, rc)
SUB NextPerm(A(),N,R, rc)


●同じものをそれぞれp,q,…,r個ずつ含む総数n個（n=p+q+ … +r）のものをすべて並べる

FUNCTION PermFactorialM(B(),M)　※(p+q+ … +r)!/(p!*q!* … *r!)
FUNCTION PermFactorialM2Num(A(),N,B(),M)
SUB Num2PermFactorialM(h, A(),N,B(),M)
SUB PrevPermFactorial(A(),N, rc)　※全順列と同じ
SUB NextPermFactorial(A(),N, rc)　※全順列と同じ


●異なるn個のものから重複を許してr個を取り出して並べる（重複順列）

N^R
FUNCTION ReptPerm2Num(A(),N,R)
SUB Num2ReptPerm(h, A(),N,R)
SUB PrevReptPerm(A(),N,R, rc)
SUB NextReptPerm(A(),N,R, rc)


●異なるn個のものをすべて円形に並べる（円順列）

FACT(N-1)　※組み込み関数
？
？
？
？


●異なるn個のものをすべて円形に並べる（左右対称なものは除く）（数珠順列）

FACT(N-1)/2　※組み込み関数
？
？
？
？


組合せ

●異なるn個のものから重複を許さずr個を取り出す組合せ

COMB(N,R)　※組み込み関数
FUNCTION Comb2Num(A(),N,R)
SUB Num2Comb(h, A(),N,R)
SUB PrevComb(A(),N,R, rc)
SUB NextComb(A(),N,R, rc)


●異なるn個のものから重複を許してr個を取り出す組合せ（重複組合せ）

COMB(N+R-1,R)　※組み込み関数
FUNCTION ReptComb2Num(A(),N,R)
SUB Num2ReptComb(h, A(),N,R)
SUB PrevReptComb(A(),N,R, rc)
SUB NextReptComb(A(),N,R, rc)

LET N=5
LET R=3

DIM A(R) !最初のパターン
FOR i=1 TO R !初期値 A={1,1,1,…,1}　※重複組合せ
   LET A(i)=1
NEXT i

LET s=0 !番号付け　０～
DO
   PRINT "No.";s
   MAT PRINT A;

   PRINT ReptComb2Num(A,N,R) !符号化

   DIM AA(R)
   MAT AA=ZER
   CALL Num2ReptComb(s,AA,N,R) !復号化
   MAT PRINT AA;

   CALL NextReptComb(A,N,R, rc) !次へ
   LET s=s+1
LOOP WHILE rc<>0
PRINT


LET s=COMB(N+R-1,R)-1 !場合の数　nHr=n+r-1Cr
DO
   PRINT "No.";s
   MAT PRINT A;
   CALL PrevReptComb(A,N,R, rc)
   LET s=s-1
LOOP WHILE rc<>0


END


!最小完全ハッシュ関数 factoradic

!●異なるn個のものをすべて並べる　※{1,2,3,…,n}上の全順列（n-順列）

!n!通りの順列パターン ⇔ 0～(n!-1)の番号

EXTERNAL FUNCTION PermFactorial2Num(A(),N) !順列パターンに番号を付ける　※辞書式順序
FOR j=1 TO N-1 !階乗進数の各桁の値＋１　A[1..N]=(N-1)! … 3! 2! 1! 0!
   FOR k=j+1 TO N
      IF A(k)>=A(j) THEN LET A(k)=A(k)-1
   NEXT k
NEXT j
LET v=0
FOR j=N TO 1 STEP -1 !非負の10進数整数へ
   LET v=v*j+A(N-j+1)-1
NEXT j
LET PermFactorial2Num=v
END FUNCTION

EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する　※辞書式順序
LET v=h !非負の10進数整数を階乗進数へ
FOR j=1 TO N
   LET t=INT(v/j)
   LET A(N-j+1)=v-t*j +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


EXTERNAL SUB PrevPermFactorial(A(),N, rc) !辞書式順序で次の順列を返す
LET rc=0 !完了

LET i=N-1 !順列を右から左にみて、増加列から減少列に変わる位置iを探す
DO WHILE i>0 AND A(i)<=A(i+1) !０は番人
   LET i=i-1
LOOP
IF i=0 THEN EXIT SUB !A(1)>A(2)>A(3)> … >A(N)なら　例. N=4、4,3,2,1

LET j=N !その位置iより右で、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

EXTERNAL SUB NextPermFactorial(A(),N, rc) !辞書式順序で次の順列を返す
LET rc=0 !完了

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 EXIT SUB !A(1)>A(2)>A(3)> … >A(N)なら　例. N=4、4,3,2,1

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


!●異なるn個のものから重複を許さずr個を取り出して並べる　※{1,2,3,…,n}上のr-順列

!perm(n,r)通りの順列パターン ⇔ 0 ～ perm(n,r)-1 の番号

EXTERNAL FUNCTION Perm2Num(A(),N,R) !順列パターンに番号を付ける　※辞書式順序
FOR j=1 TO R-1 !(階乗)進数の各桁の値＋１　A[1..R]=PERM(N-1,R-1) … PERM(N-j,R-j) … PERM(N-R,0)
   FOR k=j+1 TO R
      IF A(k)>=A(j) THEN LET A(k)=A(k)-1
   NEXT k
NEXT j
LET v=0
FOR j=R TO 1 STEP -1 !非負の10進数整数へ
   LET v=v*(N-R+j)+A(R-j+1)-1
NEXT j
LET Perm2Num=v
END FUNCTION

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


EXTERNAL SUB PrevPerm(A(),N,R, rc) !辞書式順序で前の順列を返す
LET rc=0 !完了

FOR j=1 TO R-1 !(階乗)進数へ
   FOR k=j+1 TO R
      IF A(k)>=A(j) THEN LET A(k)=A(k)-1
   NEXT k
NEXT j

FOR i=R TO 1 STEP -1 !(階乗)進数で－１する
   IF A(i)>1 THEN !1～(N-i+1)で更新する
      LET A(i)=A(i)-1
      FOR k=i+1 TO R !ｉ桁より下の位を「最後の並び」にする
         LET A(k)=N-k+1
      NEXT k

      LET rc=1 !未了
      EXIT FOR
   END IF
NEXT i

FOR j=R-1 TO 1 STEP -1 !順列パターンへ
   FOR k=j+1 TO R
      IF A(k)>=A(j) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB

EXTERNAL SUB NextPerm(A(),N,R, rc) !辞書式順序で次の順列を返す
LET rc=0 !完了

FOR j=1 TO R-1 !(階乗)進数へ
   FOR k=j+1 TO R
      IF A(k)>=A(j) THEN LET A(k)=A(k)-1
   NEXT k
NEXT j

FOR i=R TO 1 STEP -1 !(階乗)進数で＋１する
   IF A(i)<N-i+1 THEN !1～(N-i+1)で更新する
      LET A(i)=A(i)+1
      FOR k=i+1 TO R !ｉ桁より下の位を「最初の並び」にする
         LET A(k)=1
      NEXT k

      LET rc=1 !未了
      EXIT FOR
   END IF
NEXT i

FOR j=R-1 TO 1 STEP -1 !順列パターンへ
   FOR k=j+1 TO R
      IF A(k)>=A(j) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB

!●同じものをそれぞれp,q,…,r個ずつ含む総数n個（n=p+q+ … +r）のものをすべて並べる

!(p+q+ … +r)!/(p!*q!* … *r!)通りの順列パターン ⇔ 0～(p+q+ … +r)!/(p!*q!* … *r!)-1の番号

EXTERNAL FUNCTION PermFactorialM(B(),M) !同じものを含む順列の「場合の数」
LET s=B(M) !総数 r, … ,q+ … +r,p+q+ … +r
LET t=1 !組合せ comb(r,r), … ,comb(q+ … +r,q),comb(p+q+ … +r,p)
FOR i=M-1 TO 1 STEP -1
   LET s=s+B(i)
   LET t=t*COMB(s,B(i)) !組合せ順列
NEXT i
LET PermFactorialM=t
!!!別解
!!!LET s=B(1) !総数 p+q+ … +r
!!!LET t=FACT(B(1)) !階乗の積 p!*q!* … *r!
!!!FOR i=2 TO M
!!!   LET s=s+B(i)
!!!   LET t=t*FACT(B(i))
!!!NEXT i
!!!LET PermFactorialM=FACT(s)/t
END FUNCTION


EXTERNAL FUNCTION PermFactorialM2Num(A(),N,B(),M) !順列パターンに番号を付ける　※辞書式順序
DIM w(M)
MAT w=B !copy it
LET v=0
FOR i=1 TO N-1 !左端に着目する
   LET t=A(i)
   FOR j=1 TO t-1 !左端を１～A(i)-1として
      IF w(j)>0 THEN !その左端を除いた残りで最大の順列をつくる
         LET w(j)=w(j)-1
         !!!MAT PRINT w; !debug
         LET v=v+PermFactorialM(w,M) !その順列の番号を求める
         LET w(j)=w(j)+1
      END IF
   NEXT j
   LET w(t)=w(t)-1 !左端を消して、次へ
NEXT i
LET PermFactorialM2Num=v
END FUNCTION

EXTERNAL SUB Num2PermFactorialM(h, A(),N,B(),M) !番号から順列パターンを生成する　※辞書式順序
DIM w(M)
MAT w=B !copy it
LET v=h
FOR i=1 TO N
   FOR j=1 TO M !左端を１～Mとして
      IF w(j)>0 THEN !その左端を除いた残りで最大の順列をつくる
         LET w(j)=w(j)-1
         !!!MAT PRINT w;
         LET t=PermFactorialM(w,M) !その順列の番号を求める
         IF v<t THEN EXIT FOR
         LET v=v-t
         LET w(j)=w(j)+1
      END IF
   NEXT j
   LET A(i)=j !次へ
NEXT i
END SUB


!●異なるn個のものから重複を許してr個を取り出して並べる（重複順列）

!N^R通りの順列パターン ⇔ 0 ～ N^R-1 の番号

EXTERNAL FUNCTION ReptPerm2Num(A(),N,R) !順列パターンに番号を付ける　※辞書式順序
LET v=A(1)-1
FOR i=2 TO R !N進法R桁の数を10進法へ
   LET v=v*N+A(i)-1
NEXT i
LET ReptPerm2Num=v
END FUNCTION

EXTERNAL SUB Num2ReptPerm(h, A(),N,R) !番号から順列パターンを生成する　※辞書式順序
LET v=h
LET i=R !桁位置
DO UNTIL v=0 !10進法の数をN進法R桁へ
   LET t=INT(v/N)
   LET A(i)=v-t*N+1 !1～N　※剰余
   LET v=t
   LET i=i-1
LOOP
FOR k=i TO 1 STEP -1 !残りの桁を埋める
   LET A(k)=1
NEXT k
END SUB


EXTERNAL SUB PrevReptPerm(A(),N,R, rc) !辞書式順序で前の順列を返す
LET rc=0 !完了
FOR i=R TO 1 STEP -1 !N進法R桁の数として
   IF A(i)>1 THEN !1～Nで更新する
      LET A(i)=A(i)-1
      FOR j=i+1 TO R !A(i)=A(i+1)= … =A(R)　最後の並び
         LET A(j)=N
      NEXT j
      LET rc=1 !未了
      EXIT SUB
   END IF
NEXT i
END SUB

EXTERNAL SUB NextReptPerm(A(),N,R, rc) !辞書式順序で次の順列を返す
LET rc=0 !完了
FOR i=R TO 1 STEP -1 !N進法R桁の数として
   IF A(i)<N THEN !1～Nで更新する
      LET A(i)=A(i)+1
      FOR j=i+1 TO R !A(i)=A(i+1)= … =A(R)　最初の並び
         LET A(j)=1
      NEXT j
      LET rc=1 !未了
      EXIT SUB
   END IF
NEXT i
END SUB



!最小完全ハッシュ関数 combinadic

!●異なるn個のものから重複を許さずr個を取り出す組合せ

!comb(n,r)通りの組合せパターン ⇔ 0 ～ comb(n,r)-1 の番号

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

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


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

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

EXTERNAL SUB PrevComb(A(),N,R, rc) !辞書式順序で前の組合せを返す
LET rc=0 !完了
FOR i=R TO 2 STEP -1 !並びの差が２以上の位置を探す
   IF A(i)-A(i-1)>1 THEN EXIT FOR
NEXT i
IF i>1 OR (i=1 AND A(1)>1) THEN
   LET A(i)=A(i)-1
   FOR j=i+1 TO R !A(2)=N-R+2< … A(R-1)=N-1<A(R)=N　最後の並び
      LET A(j)=N-R+j
   NEXT j
   LET rc=1 !未了
END IF
END SUB

EXTERNAL SUB NextComb(A(),N,R, rc) !辞書式順序で次の組合せを返す
LET rc=0 !完了
FOR i=R TO 1 STEP -1
   IF A(i)<N-R+i THEN !i～N-R+iで更新する
      LET A(i)=A(i)+1
      FOR j=i+1 TO R !A(i)<A(i+1)< … <A(R)　最初の並び
         LET A(j)=A(j-1)+1
      NEXT j
      LET rc=1 !未了
      EXIT SUB
   END IF
NEXT i
END SUB


!●異なるn個のものから重複を許してr個を取り出す組合せ（重複組合せ）

!comb(n+r-1,r)通りの組合せパターン ⇔ 0 ～ comb(n+r-1,r)-1 の番号

!※Homogeneous Product、nHr=comb(n+r-1,r)=comb(n+r-1,n-1)

EXTERNAL FUNCTION ReptComb2Num(A(),N,R) !組合せパターンに番号を付ける　※辞書式順序
LET v=COMB(N+R-1,R)-1
FOR j=R-1 TO 0 STEP -1
   LET t=N-A(R-j) !0～N-1
   LET v=v-COMB(t+j,j+1) !tHj+1
NEXT j
LET ReptComb2Num=v
!!!別解
!!!FOR j=1 TO R
!!!   LET t=N-A(j) !0～N-1
!!!   LET v=v-COMB(t+R-j,R-j+1) !tHr-j+1
!!!NEXT j
!!!LET ReptComb2Num=v
END FUNCTION

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


EXTERNAL SUB PrevReptComb(A(),N,R, rc) !辞書式順序で前の組合せを返す
LET rc=0 !完了
FOR i=R TO 2 STEP -1 !並びの差が１以上の位置を探す
   IF A(i)-A(i-1)>0 THEN EXIT FOR
NEXT i
IF i>1 OR (i=1 AND A(1)>1) THEN
   LET A(i)=A(i)-1
   FOR j=i+1 TO R !A(i+1)= … A(R-1)=A(R)=N　最後の並び
      LET A(j)=N
   NEXT j
   LET rc=1 !未了
END IF
END SUB

EXTERNAL SUB NextReptComb(A(),N,R, rc) !辞書式順序で次の組合せを返す
LET rc=0 !完了
FOR i=R TO 1 STEP -1
   IF A(i)<N THEN !i～Nで更新する
      LET A(i)=A(i)+1
      FOR j=i+1 TO R !A(i)=A(i+1)= … =A(R)　最初の並び
         LET A(j)=A(j-1)
      NEXT j
      LET rc=1 !未了
      EXIT SUB
   END IF
NEXT i
END SUB