順列生成(一般順列)問題(2)を紹介します。
問題(2)
集合{1,1,2,2,3}上の一般順列を辞書式順序で列挙せよ。
順列生成(一般順列)問題(2)を紹介します。
問題(2)
集合{1,1,2,2,3}上の一般順列を辞書式順序で列挙せよ。
順列生成(一般順列)問題(1)の考察1を示します。
問題(1)の考察1
' << GP111.bas >> ' 考察1に基づく一般順列生成プログラム。 ' Tiny Basic ' Public A(99): ' 集合{1,2,...,r}上の順列を保存する配列。 Public B(99): ' B(i):要素i(1≦i≦n)の個数。 Public C(99): ' C(g)はグループ番号gに含まれる要素が昇順に ' 出現しているかどうか監視する。 ' 出現するたびに1つ増加する。 Public G(99): ' 要素i(1≦i≦r)が属するグループ番号G(i)。 Public N: ' 集合の要素数。 Public R: ' 一般順列の長さ。 Public COUNT ' 一般順列の個数。 ' Do ' 要素数nの読み込み。 Read N If (N <= 0) or (N > 99) Then Exit Do ' ' 各要素の個数の入力。 B(0)=0 For I=1 To N: Read B(I): Next I ' Data 2, 2,2 Data 3, 2,2,1 DAta 0 ' ' 一般順列の長さの計算。 R=0 For I=1 To N: R=R+B(I): Next I If R > 99 Then Stop ' ' 配列Gの初期設定。 ' {1,2,…,r}上の順列の各要素にグループ番号を割り当てる。 K=0 For I=1 To N For J=1 To B(I): K=K+1: G(K)=I: Next J Next I ' ' 配列Cの初期設定。 ' グループ内で昇順を保証する配列の初期設定。 C(1)=1 For I=2 To N: C(I)=C(I-1)+B(I-1): Next I ' ' 配列Aの初期設定。 For I=0 To R: A(I)=I: Next I COUNT=0 ' ' 一般順列の生成。 Call Perm(0) ' ' 実行結果。 Print Using"集合の要素数###";N For I=1 To N Print Using"要素## 個数##";I;B(I) Next I Print "一般順列の個数:";COUNT Print Loop End ' ' 一般順列を生成する再帰手続き。 Sub Perm(K) If K = R Then ' 一般順列の出力。 COUNT=COUNT+1 Print Using"#####: ";COUNT; For I=1 To R: Print Using"##";G(A(I));: Next I Print Exit Sub End If ' ' 深さKの節点から深さK+1の子節点をN-K個作成する。 For I=K+1 To R W=A(K+1): A(K+1)=A(I): A(I)=W ' グループ内で昇順が確認された場合、深さK+1の子節点に進む。 If C(G(A(K+1))) = A(K+1) Then C(G(A(K+1)))=C(G(A(K+1)))+1 ' 深さK+1の子節点を作成する。 Call Perm(K+1) C(G(A(K+1)))=C(G(A(K+1)))-1 End If ' 深さKの親節点に戻す。 W=A(K+1): A(K+1)=A(I): A(I)=W Next I End Sub
順列生成(一般順列)問題(1)の解答例を示します。
問題(1)の解
順列生成(一般順列)問題(1)を紹介します。
問題(1)
順列生成(選択法)問題(5)の解答例を示します。
問題(5)の解
' << SE501.bas >> ' ランダム部分順列生成プログラム。 ' Tiny Basic ' Public A(9) ' ランダム部分順列を保存する配列。 Public N ' 要素数。 Public R ' 取り出す要素数。 Public COUNT ' 生成されたランダム部分順列の個数。 ' Do ' N,Rの読み込み。 Read N,R If (N <= 0) or (R > N) Then Exit Do Data 5,3, 0,0 ' COUNT=0 For I=1 To 10 ' 初期設定。 For J=1 To N: A(J)=J: Next J ' ' ランダム部分順列生成。 Call Perm(0) Next I ' 結果の表示。 Print Using"N=## R=## COUNT=######";N;R;COUNT Loop End ' ' 部分順列を生成する再帰手続き。 ' Kは木の深さを表す。 Sub Perm(K) ' 生成された部分順列の表示。 If( K = R ) Then COUNT=COUNT+1 Print Using"###: ";COUNT; For I=1 To R: Print Using"##";A(I);: Next I Print Exit Sub End If ' ' Jは交換する位置。 J=Int(Rnd(1)*(N-K))+K+1 ' J番目とK+1番目の要素を交換する。 W=A(J): A(J)=A(K+1): A(K+1)=W ' 深さK+1の子節点を作成する。 Call Perm(K+1) End Sub
順列生成(選択法)問題(5)を紹介します。
問題(5)
n個の要素{1,2,…,n}からr個取り出し,1列に並べる部分順列をランダムに
生成する方法を考えよ。
順列生成(選択法)問題(4)の考察2を示します。
問題(4)の考察2