久々に1日半ぐらい頭を使ったので、同じお題に直面した方に向けて、私なりの解法を書いてみます。
お題
同種のモノがn個あるとき、nを一度に運ぶこともあれば、半分ずつ2回に分けて運ぶこともあったり、1個ずつn回に分けて運ぶこともある、みたいな場合に、そのありうる組合せを出せ。
例えば、nが5の場合は、(5,),(4,1),(3,2),(3,1,1),(2,2,1),(2,1,1,1),(1,1,1,1,1)の7通り。
何ていう問題？
文系の私は高校卒後以来30年近く数学に触れていなかったので、「白玉と赤玉の組合せパターンみたいな問題があったなぁ」ぐらいの記憶しかなく、問題の名前すら全く思い出せませんでした。。。そこで、少しググると、「組分け問題」という名前らしいということがわかりました。
私の遠い記憶では、「場合の数」が数式でサクッと出せるイメージだったのですが、どうやらこの問題は上記のリンクの「組分け問題のパターン」の（12）にあたるので、「書き出し」という解決法だということが分かりました。そうでしたか、力技でしたか。
私の解法のアプローチ
いろいろ試行錯誤した割には、シンプルというか、大したことないものになりました。
- 数字を入れるリスト（numbers）を用意し、heapqのリストにして、n（例えば3）を入れる
- numbersがn（例えば3）なら、その数字のみ戻す（例えば(3,)）
- numbersから3を取り出して、1を引いて（例えば2）numbersに入れる（numbers=[2]）
- numbersの数字の合計は2でn（例えば3）に満たないので、同じ数字（例えば2）を入れる（同じ数字を入れるのは、nが4のような場合に（2,2）の組み合わせがあるため）
- すると、numbersは[2,2]になり合計値がn（例えば3）を超えるので、最小値を取り出して1を引いて（例えば1）、numbersに入れる
- すると、numbersは[2,1]になり合計値がn（例えば3）になるので、その組み合わせ（2,1）を戻す
- そこから最小値（例えば1）を取り出し1を引きたいところだがゼロになってしまうので、numbersからもう１個数字を取り出し（例えば2）、1を引いて（例えば、1）numbersに入れる（numbers=[1]）
- numbersの合計値がn（例えば3）に満たないので、同じ数字を入れる（numbers=[1,1])
- まだ合計値に満たないので同じ数字を入れる（numbers=[1,1,1]）
- 合計値がn（例えば3）になったので、その組み合わせ（1,1,1）を戻す
- そこから最小値を取り出して1を引きたいところだがゼロになるので、次の最小値を取り出す。1を引きたいところだがゼロになってしまうので次の最小値を取り出す。1を引きたいところだがゼロになってしまうので次の最小値を取り出したいところだが、numbersに数字がなくなってしまったので終了。
以上のように書き出すと大変そうですが、コードにするとスッキリします。
import heapq
def divide_number(n):
"""n個のものを1回または複数回に分けて運ぶ場合のパターン。例えば、n =3のとき、(3,), (2, 1), (1, 1, 1)。戻り値の型はgenerator。"""
if n <1: return []
numbers = []
heapq.heappush(numbers, n)
while numbers:
if sum(numbers) < n:
heapq.heappush(numbers, numbers[0])
else:
if sum(numbers) == n:
yield tuple(sorted(numbers, reverse= True)) # generatorを返す
smallest = heapq.heappop(numbers)
while smallest == 1 and numbers:
smallest = heapq.heappop(numbers)
if smallest >1: heapq.heappush(numbers, smallest -1)
あまり使い途が無いかもしれませんが、誰かのお役に立てれば幸いです。