全組み合わせを生成するには？

 投稿者：ひいらぎ  投稿日：2010年 2月24日(水)13時19分21秒
  はじめまして
つい最近このサイトを知りました。
初歩的なことですみませんが、以下のようにするには
どうすればいいかお教え頂けないでしょうか？

n個のビット列でr個の1を含むパターンの総数nＣrに
通し番号をつけて生成する、というものです。

例えば、5桁のうち3個の1がある場合、
　A(1)=00111, A(2)=01011, ……, A(10)=11100
という具合です。または十進にして、
　A(1)=7, A(2)=11, ……, A(10)=28
でもいいです。
大きさの順はランダムでかまいません。
とにかく全ての場合を任意に取り出したいのです。

プログラム初心者の質問で申し訳ないですが、
ご教授よろしくお願い致します。 		 

Re: 全組み合わせを生成するには？

 投稿者：山中和義  投稿日：2010年 2月24日(水)14時18分8秒
  > No.1046[元記事へ]

ひいらぎさんへのお返事です。

> n個のビット列でr個の1を含むパターンの総数nＣrに
> 通し番号をつけて生成する、というものです。
LET N=5
LET R=3
FOR i=0 TO COMB(N,R)-1 !全パターン
   PRINT i
   CALL Num2Comb(i,A,N,R) !番号は０～
   PRINT BSTR$(A,2); A
NEXT i
END

EXTERNAL SUB Num2Comb(h, A,N,R) !番号から組合せパターンを生成する　※辞書式順序
LET v=COMB(N,R)-h
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^(N-i-1) !ビット位置(N-i-1)を１とする
      LET j=j-1
      LET v=v-t
   END IF
NEXT i
END SUB

集合A={1,2,3,4,5}
　{1,2,3}
　{1,2,4}
　　：
　{4,5,6}
では、こちら（No.675 [元記事へ]）を参照してください。 		 

戻る