順列生成（応用）問題（２）の解答例を示します。
問題（２）の解
今日で、７年目に入りました。
コロナウィルスとの遭遇を避け、自宅でひっそりと過ごす毎日です。
テニスのレッスンも中断しています。運動不足が気になります。
現在、「順列生成」というテーマで投稿しています。
「再帰」という考え方に興味を持ち、プログラムを収集していたら、
かなりの量になり、整理したものです。
プログラミングの面白さも実感してもらえるのではと、
プログラムも付けています。
コロナの収束を願いつつ、個人や社会が大きく変わる
時代になったのかなと感じています。
順列生成（応用）問題（２）を紹介します。
問題（２）
集合{1,2,…,n}の部分集合を考察する。
集合{1,2,3,4,5}の部分集合を列挙せよ。
順列生成（応用）問題（１）の考察１を示します。
問題（１）の考察１
' << COM111.bas >>
' 問題（１）の考察１に基づくプログラム。
' Tiny Basic
'
Public A(9) ' 組み合わせを保存する配列。
Public N ' 要素数。
Public R ' 取り出す要素数。
Public COUNT ' 生成された組み合わせの個数。
'
Do
' N,Rの読み込み。
Read N,R
If (N <= 0) or (N > 9) Then Exit Do
Data 5,3, 0,0
'
' 配列Aの初期設定。
For I=0 To N: A(I)=I: Next I
'
' 初期設定。
COUNT=0
'
' 組み合わせ生成。
Call Perm(0)
'
' 結果の表示。
Print Using"N=## R=##";N;R
Print "COUNT=";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
' 深さKの節点から深さK+1の子節点 N-K個を生成する。
For I=K+1 To N
If A(K) < A(I) Then
' I番目とK+1番目の要素を交換する。
W=A(I): A(I)=A(K+1): A(K+1)=W
' 深さK+1の子節点を作成する。
Call Perm(K+1)
' 交換を戻す。
W=A(I): A(I)=A(K+1): A(K+1)=W
End If
Next I
End Sub
順列生成（応用）問題（１）の解答例を示します。
問題（１）の解
順列生成（応用）問題（１）を紹介します。
問題（１）
集合{1,2,…,n}からr個取り出す組合せを考察する。
集合{1,2,3,4,5}から3個取り出す組合せを列挙せよ。
順列生成（一般順列）問題（２）の考察１を示します。
問題（２）の考察１
選択法で辞書式順序に順列を生成する方法を使って、一般順列を生成する。
' << GP211.bas >>
' 考察２に基づく一般順列生成プログラム。
' Tiny Basic
'
Public A(99): ' 集合{1,2,...,r}上の順列を保存する配列。
Public B(99): ' B(i):要素i(1≦i≦n)の個数。
Public C(99): ' C(g)はグループ番号gに含まれる要素が昇順に
' 出現しているかどうか監視する。
' 出現するたびに１つ増加する。
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
' I番目とK+1番目の要素を交換する。
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
Next I
' 交換を戻す。
T=A(K+1)
For J=K+2 To R: A(J-1)=A(J): Next J
A(R)=T
End Sub 
順列生成（一般順列）問題（２）の解答例を示します。
問題（２）の解
