資料


subsetsum

#解の個数
def number_of_solution(size, target = None):
    """
    引数1:アイテムのサイズリスト,引数2:subsetsumのtarget
    返り値 :引数1つの場合はPartitionの解となる部分集合の個数
          :引数2つの場合はtargetとなる部分集合の個数
    """
    #第2引数が与えられていない場合はPartition
    if target is None:
        target = sum(size)//2
    #テーブルの作成
    table = [[0 for j in range(target+1)] for i in range(len(size))]
    for j in range(target+1):
        for i in range(len(size)):
            #1つ目の要素
            if i == 0:
                if j == 0 or j == size[i]:
                    table[i][j] = 1
            #2つ目以降の要素
            else:
                if j >= size[i]:
                    table[i][j] = table[i-1][j-size[i]] + table[i-1][j]
                else:
                    table[i][j] = table[i-1][j]
    #print(table)
    return table[i][j]
 
 
#解の種類の個数
import collections
def kind_of_solution(size ,target = None):
    """
    引数1:アイテムのサイズリスト,引数2:subsetsumのtarget
    返り値 :引数1つの場合はPartitionの解の種類の個数
          :引数2つの場合はtargetとなる種類の個数
    """
    #第2引数が与えられていない場合はPartition
    if target is None:
        target = sum(size)//2
    #アイテムのサイズごとの個数を持つ辞書
    number_of_items = collections.Counter(size)
    #アイテムのサイズを持つリスト
    number_of_types = list(number_of_items.keys())
    #テーブルの作成
    table = [[0 for j in range(target+1)] for i in range(len(number_of_types))]
 
    for j in range(target+1):
        for i in range(len(number_of_types)):
            #1つ目の要素
            if i==0:
                for k in range(number_of_items[number_of_types[i]]+1):
                    if k*number_of_types[i] == j:
                        table[i][j] = 1
            #2つ目以降の要素
            else:
                table[i][j] = sum(table[i-1][j-k*number_of_types[i]] for k in range(number_of_items[number_of_types[i]]+1) if j >= k*number_of_types[i])
    #print(table)
    return table[i][j]
 
 
 
size = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4]
print(number_of_solution(size,495))
print(number_of_solution(size))
print(kind_of_solution(size))
 


Pythonのジェネレータ関数


  1. 無限に要素を生成するジェネレータ関数のサンプルプログラムを Python Tutor で動かす
  2. 「自然数 8 の分割」の総数、および、そのうち各要素がすべて奇数であるものの数を数え上げるサンプルプログラムを Python Tutor で動かす