コラム

再帰処理(2)

作成日:20200711  テーマ1:情報系  テーマ2:プログラム  テーマ3:

苦手な再帰処理について、自分が理解したプロセスを備忘録的に残しておく。

今回は、以下の(a1,a2)、(b1,b2,b3,b4)、(c1,c2)の各列から1つずつ選んで“重複なしの組み合わせ”を、再帰処理を使って書いて見る。

再帰処理
プログラムが長いと見る気をなくしてしまうが、一応次のようにモジュールを分けている。 従って、一つ一つのモジュールは大して長くないので我慢してみてもらえれば、と思う。

< python >

#***********************************************************
#sampleデータ作成
#	ここを編集すれば組み合わせの数、データをいろいろ変えられる
#***********************************************************
def MakeData():
	dAry = []
	
	#データa
	dAry.append(['a1', 'a2', 'a3'])
	
	#データb
	dAry.append(['b1', 'b2'])
	
	#データc
	dAry.append(['c1', 'c2'])
	
	return dAry

#**********************************************************
#再帰関数
#   comb    :組合せ配列
#   cntC    :組合せ配列のID(組合せ個数分)
#   dAry    :組合せ元のデータ配列
#   IDc     :データ元の番号 a=0, b=1, c=2
#   cutLv   :組合せる変数の数
#           (0にするとaのみ、1にするとaとb、2にするとa,b,cの組合せ)
#**********************************************************
def Recursion(comb, cntC, dAry, IDc, cutLv):
	
	for cnt1 in range(len(dAry[IDc])):
		comb[cntC][IDc] = dAry[IDc][cnt1]
		
		if IDc < cutLv - 1:
			cntC = Recursion(comb, cntC, dAry, IDc + 1, cutLv)
		else:
			if cntC < len(comb) - 1:
				cntC += 1
				
				#↓がないと、歯抜けデータになってしまう。
				#試しにコメントアウトしてマクロを実行してみてもらいたい。
				for cnt2 in range(IDc):
					comb[cntC][cnt2] = comb[cntC - 1][cnt2]
	
	#combCの配列IDを返す
	return cntC

#***********************************************************
#実行
#***********************************************************
if __name__ == '__main__':
	
	#サンプルデータ作成(dAry) >>>>>>>>>>>>>>>>>>>>>>
	dAry = []
	dAry = MakeData()
	
	#確認用
	print(MakeData())
	
	#再帰処理(組合せ = comb)>>>>>>>>>>>>>>>>>>>>>>>>
	#配列準備(combサイズを確定)
	Nary = 1
	for cnt1 in range(len(dAry)):
		Nary *= len(dAry[cnt1]) 
	tmp = []
	for cnt1 in range(len(dAry)):
		tmp.append('')
	comb = []
	for cnt1 in range(Nary):
		comb.append(tmp.copy())		#copyしないと全部同じ要素になる
	
	#再帰処理
	Recursion(comb, 0, dAry, 0, len(dAry))
	
	#出力 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	for rcomb in comb:
		print(rcomb)

pythonサンプルのダウンロード


< Excel VBA >

'**********************************************************
'sampleデータ作成
'   ここを編集すれば組み合わせの数、データをいろいろ変えられる
'**********************************************************
Sub MakeData(dAry)
    
    Dim tmp() As String
    
    '各データで行数がことなるため、ジャグ配列を使う
    ReDim dAry(2)
    
    'データa
    ReDim tmp(2)
    tmp(0) = "a1"
    tmp(1) = "a2"
    tmp(2) = "a3"
    dAry(0) = tmp
        Erase tmp
    
    'データb
    ReDim tmp(1)
    tmp(0) = "b1"
    tmp(1) = "b2"
    dAry(1) = tmp
        Erase tmp
    
    'データc
    ReDim tmp(1)
    tmp(0) = "c1"
    tmp(1) = "c2"
    dAry(2) = tmp
        Erase tmp

End Sub

'**********************************************************
'再帰関数
'   comb    :組合せ配列
'   cntC    :組合せ配列のID(組合せ個数分)
'   dAry    :組合せ元のデータ配列
'   IDc     :データ元の番号 a=0, b=1, c=2
'   cutLv   :組合せる変数の数
'           (0にするとaのみ、1にするとaとb、2にするとa,b,cの組合せ)
'**********************************************************
Sub Recursion(comb, cntC, dAry, IDc, cutLv)
    
    Dim cnt1 As Long, cnt2 As Long
    
    For cnt1 = 0 To UBound(dAry(IDc))
        comb(IDc, cntC) = dAry(IDc)(cnt1)
        
        If IDc < cutLv Then
            Call Recursion(comb, cntC, dAry, IDc + 1, cutLv)
        Else
            cntC = cntC + 1
            
            'ここで配列を追加すると、最後余分に1個配列が追加される
            ReDim Preserve comb(UBound(dAry), cntC)
            
            '↓がないと、歯抜けデータになってしまう。
            '試しにコメントアウトしてマクロを実行してみてもらいたい。
            For cnt2 = 0 To UBound(dAry)
                comb(cnt2, cntC) = comb(cnt2, cntC - 1)
            Next cnt2
        End If
    Next cnt1
End Sub

'**********************************************************
'実行
'**********************************************************
Sub test()
    
    Dim cnt1 As Long, cnt2 As Long
    Dim colNo As Long
    Dim dAry() As Variant
    Dim comb() As String
    
    'サンプルデータ作成(dAry) >>>>>>>>>>>>>>>>>
    Call MakeData(dAry)
    
    '再帰処理(組合せ = comb) >>>>>>>>>>>>>>>>>>
    '   配列は1個余計なものができてしまう(最後尾)
    ReDim Preserve comb(UBound(dAry), 0)
    Call Recursion(comb, 0, dAry, 0, UBound(dAry))
    
    'セルに出力 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    
    '前回データ消去
    Cells.ClearContents
    
    '余計な1個は出力しない
    colNo = Range("E1").Column
    For cnt1 = 0 To UBound(comb, 2) - 1
        For cnt2 = 0 To UBound(comb, 1)
            Cells(cnt1 + 1, colNo + cnt2).Value = comb(cnt2, cnt1)
        Next cnt2
    Next cnt1
End Sub

Excel VBAサンプルのダウンロード


結果は次のようになる。

再帰処理
この再帰処理の実行手順は、次のようになる。
まず、元のデータの構成とループ変数やIDとの関係は下図のようになる。

再帰処理
この関係性に基づいて、各データを配列combに入れ込んでいく手順を下図に示す。 結果の図と下図の赤文字部分を比較してみてもらいたい。同じ順番で現れているはずだ。

再帰処理
灰点線で囲われた箇所は、ソース内で「↓がないと、歯抜けデータになってしまう。・・・」部分を回避する処理で対応している。
また、上図は次のように書き換えた方がわかりやすいかもしれない。

再帰処理
以上で、再帰処理を使った"重複なしの組合せ"の話はおわりである。

VBAの癖が抜けなくて、pythonも同じような感じで書いてしまうのは...悲しい...。

コラムページトップへ