部分集合

 投稿者：山中和義  投稿日：2015年 6月11日(木)16時25分11秒
  問題
nを正整数として、集合S={1,2,3,…,n}とする。
Sの部分集合A,B,C,Dで、
　A∪B∪C∪D=S　かつ　A∩B∩C=Φ（空集合）
を満たす集合の組(A,B,C,D)は何通りあるか。
ただし、A,B,C,Dは同じもの（空集合でもよい）が重なっていてもよいものとする。


考察
整数mの2進法表記でのビットパターンを部分集合の要素の有無に対応させる。
S={1,2,3,4}に対して、ビットパターン1011なら、{1,3,4}を表すとする。
k個の要素なら、0から2^k-1の数値mで表すことができる。
（終り）


LET N=3 !nビット
LET S=2^N-1
LET T=0
FOR A=0 TO S
   FOR B=0 TO S
      FOR C=0 TO S
         IF BITAND(BITAND(A,B),C)=0 THEN !A∩B∩C=φ

            LET W=BITOR(BITOR(A,B),C) !A∪B∪C
            LET T=T+2^BITCOUNT(W) !Dの自由度
            ! または
            ! LET W=BITOR(BITOR(A,B),C) !A∪B∪C
            ! FOR D=0 TO S
            !    IF BITOR(W,D)=S THEN LET T=T+1
            ! NEXT D

         END IF
      NEXT C
   NEXT B
NEXT A
PRINT T;"通り" !13^n
END

EXTERNAL FUNCTION BITCOUNT(N) !正の整数nを2進法表記したときの1の個数を返す
LET C=0
DO WHILE N>0
   LET C=C+MOD(N,2)
   LET N=INT(N/2)
LOOP
LET BITCOUNT=C
END FUNCTION



また、A,B,C,Dがすべて異なる場合は何通りあるか。


LET N=3 !nビット
LET S=2^N-1
LET T=0
FOR A=0 TO S-2 !組(A,B,C)
   FOR B=A+1 TO S-1
      FOR C=B+1 TO S
         IF BITAND(BITAND(A,B),C)=0 THEN !A∩B∩C=φ

            LET W=BITOR(BITOR(A,B),C) !A∪B∪C
            LET T=T+2^BITCOUNT(W) !Dの自由度
            IF W=S THEN LET T=T-3
            ! または
            ! LET W=BITOR(BITOR(A,B),C) !A∪B∪C
            ! FOR D=0 TO S
            !    IF (D-A)*(D-B)*(D-C)<>0 THEN !DはA,B,Cと異なる
            !
            !       IF BITOR(W,D)=S THEN LET T=T+1
            !
            !    END IF
            ! NEXT D

         END IF
      NEXT C
   NEXT B
NEXT A
PRINT T*FACT(3);"通り"
END

EXTERNAL FUNCTION BITCOUNT(N) !正の整数nを2進法表記したときの1の個数を返す
LET C=0
DO WHILE N>0
   LET C=C+MOD(N,2)
   LET N=INT(N/2)
LOOP
LET BITCOUNT=C
END FUNCTION


 		 

Re: 部分集合

 投稿者：山中和義  投稿日：2015年 6月13日(土)10時06分41秒
  > No.3750[元記事へ]

部分集合の生成


集合A={a1,a2,a3,…,an}のとき
部分集合は、φ,{a1},{a2},…,{an},{a1,a2},…,{a1,an},…,{a1,a2,…,an}、個数は2^n個

その１

LET N=4 !A={1,2,3,4}
DIM B(N)
CALL subset(1,1,N,B)
END
EXTERNAL SUB subset(X,K, N,S()) !バックトラック法
IF X>N THEN
   PRINT "{";
   FOR i=1 TO K-1
      PRINT S(i);
   NEXT i
   PRINT "}"
ELSE
   LET S(K)=X
   CALL subset(X+1,K+1,N,S)
   CALL subset(X+1,K,N,S)
END IF
END SUB



その２　Σ[r=0,n]C(n,r)=C(n,0)+C(n,1)+C(n,2)+ … +C(n,n)=2^n

LET N=4 !A={1,2,3,4}
FOR R=0 TO N !r個の要素
   FOR K=0 TO COMB(N,R)-1
      PRINT Num2CombBit(K,N,R)
   NEXT K
   PRINT
NEXT R
END
EXTERNAL FUNCTION Num2CombBit(h,N,R) !番号から組合せビットパターンを生成する　※辞書式順序
LET v=h+1
LET j=R
LET A=0
FOR i=N-1 TO 0 STEP -1 !組合せをビット位置とする
   LET t=COMB(i,j)
   IF v>t THEN
      LET A=A+2^i !ビット位置(N-i-1)を１とする
      LET j=j-1
      LET v=v-t
   END IF
NEXT i
LET Num2CombBit=A
END FUNCTION




集合A={1,2,4}のとき
部分集合は、φ,{1},{2},{4},{1,2},{1,4},{2,4},{1,2,4}

LET A=BVAL("1101",2) !A={1,2,4}
LET Y=A
DO
   LET S=BITAND(A,Y) !a & (a-1)
   PRINT S
   LET Y=S-1
LOOP WHILE S>0
END


 		 

戻る