メモ

千円札、五百円、百円硬貨を使って3000円を支払う方法は何通りあるか

問題 Python

detail.chiebukuro.yahoo.co.jp

順列（再帰）

def perm(head, money):

    coin = [100, 500, 1000]

    if money == 0:

        return [head]

    else:

        res = []

        for i in coin:

            if money - i < 0:
                break

            headx = head + [i]

            res += perm(headx, money - i)

        return res

# 3000円になる順列作成
data = perm([], 3000)
# print(len(data))

# リスト内ソート、重複除去
tp = set(map(tuple, map(sorted, data)))

print(len(tp))

順列（再帰2）

100×5にして回数減らす

def perm(head, money):

    coin = [100 * 5, 500, 1000]


    if money == 0:

        return [head]

    else:

        res = []

        for i, j in enumerate(coin):

            if money - j < 0:
                break

            headx = head + [j] if i else head + [100] * 5

            res += perm(headx, money - j)

        return res

# 3000円になる順列作成
data = perm([], 3000)
print(len(data))

# リスト内ソート、重複除去
tp = set(map(tuple, map(sorted, data)))

print(len(tp))

組合せ

1000円の組合せ

1000
500×2
500・100×5
100×10

1～4の組合せを作成

10.1. itertools — 効率的なループ実行のためのイテレータ生成関数 — Python 3.5.2 ドキュメント

組合せ重複あり

combinations_with_replacement()

import itertools

# 組合せ作成後、リスト平坦化
data =[ sum(i, []) for i in itertools.combinations_with_replacement([[1000],[500,500],[500]+[100]*5,[100]*10], 3)]

# リスト内ソート、重複除去
tp = set(map(tuple, map(sorted, data)))

print(len(tp))