6

Project Eulerの問題 240 を解決しようとしています:

12 面ダイス (1 から 12 までの番号が付けられた面) を 20 個振って、上位 10 個の合計を 70 にする方法は何通りありますか?

これを解決するためのコードを思いつきました。しかし、実際には計算に多くの時間がかかります。私はこのアプローチがかなり悪いことを知っています。このコードを修正してパフォーマンスを向上させる方法を教えてもらえますか?

import itertools
def check(a,b):   # check all the elements in a list a, are lesser than or equal to value b
    chk=0
    for x in a:
        if x<=b:
            chk=1
    return chk

lst=[]
count=0
for x in itertools.product(range(1,13),repeat=20):
    a=sorted([x[y] for y in range(20)])
    if sum(a[-10:])==70 and check(a[:10],min(a[-10:])):
        count+=1

以下のコードは、問題の説明で定義されている問題のコードです。それは完全に機能し、正確な解決策を提供します....

import itertools
def check(a,b):
     chk=1
     for x in a:
         if x>b:
             chk=0
             break
     return chk


count=0
for x in itertools.product(range(1,7),repeat=5):
    a=sorted([x[y] for y in range(5)])
    if sum(a[-3:])==15 and check(a[:2],min(a[-3:])):
        count+=1
4

2 に答える 2

12

It's no good iterating over all possibilities, because there are 1220 = 3833759992447475122176 ways to roll 20 twelve-sided dice, and at, say, a million rolls per second, that would take millions of years to complete.

The way to solve this kind of problem is to use dynamic programming. Find some way to split up your problem into the sum of several smaller problems, and build up a table of the answers to these sub-problems until you can compute the result you need.

For example, let T(n, d, k, t) be the number of ways to roll n d-sided dice so that the top k of them sum to t. How can we split this up into sub-problems? Well, we could consider the number of dice, i, that roll d exactly. There are nCi ways to choose these i dice, and T(n − i, d − 1, ...) ways to choose the n − i remaining dice which must roll at most d − 1. (For some suitable choice of parameters for k and t which I've elided.)

Take the product of these, and sum it up for all suitable values of i and you're done. (Well, not quite done: you have to specify the base cases, but that should be easy.)

The number of sub-problems that you need to compute will be at most (n + 1)(d + 1)(k + 1)(t + 1), which in the Project Euler case (n = 20, d = 12, k = 10, t = 70) is at most 213213. (In practice, it's much less than this, because many branches of the tree reach base cases quickly: in my implementation it turns out that the answers to just 791 sub-problems are sufficient to compute the answer.)

To write a dynamic program, it's usually easiest to express it recursively and use memoization to avoid re-computing the answer to sub-problems. In Python you could use the @functools.lru_cache decorator.

So the skeleton of your program could look like this. I've replaced the crucial details by ??? so as not to deprive you of the pleasure of working it out for yourself. Work with small examples (e.g. "two 6-sided dice, the top 1 of which sums to 6") to check that your logic is correct, before trying bigger cases.

def combinations(n, k):
    """Return C(n, k), the number of combinations of k out of n."""
    c = 1
    k = min(k, n - k)
    for i in range(1, k + 1):
        c *= (n - k + i)
        c //= i
    return c

@lru_cache(maxsize=None)
def T(n, d, k, t):
    """Return the number of ways n distinguishable d-sided dice can be
    rolled so that the top k dice sum to t.

    """
    # Base cases
    if ???: return 1
    if ???: return 0

    # Divide and conquer. Let N be the maximum number of dice that
    # can roll exactly d.
    N = ???
    return sum(combinations(n, i)
               * T(n - i, d - 1, ???)
               for i in range(N + 1))

With appropriate choices for all the ???, this answers the Project Euler problem in a few milliseconds:

>>> from timeit import timeit
>>> timeit(lambda:T(20, 12, 10, 70), number=1)
0.008017531014047563
>>> T.cache_info()
CacheInfo(hits=1844, misses=791, maxsize=None, currsize=791)
于 2012-12-12T11:59:35.260 に答える
0

このソリューションは機能するはずです-システムでどれくらいの時間がかかるかわかりません。

from itertools import product

lg = (p for p in product(xrange(1,13,1),repeat=10) if sum(p) == 70)

results = {}
for l in lg:
    results[l] = [p for p in product(xrange(1,min(l),1),repeat=10)]

最初に「トップ10」を作成します。次に、各「トップ10」に、可能な「次の10」アイテムのリストを追加します。このリストでは、最大値が「トップ10」の最小アイテムに制限されています。

結果は、keyが「トップ10」であり、値が可能な「次の10」のリストである辞書です。

解決策（要件に適合する組み合わせの量）は、次のようにすべての結果dictのリストの数を数えることです。

count = 0
for k, v in results.items():    
    count += len(v)

そしてcount結果になります。

アップデート

さて、私はこれを行うための少し良い方法を考えました。

from itertools import product
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_count = dict((n, math.pow(n, dice-top)) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

「次の10」の長さだけを数えるので、「トップ10」の「最小」の数値ごとにオプションの量を事前に計算するだけだと思ったので、それを行う辞書を作成しました。上記のコードは、小さな辞書、カウンター、およびジェネレーターのみで構成されているため、はるかにスムーズに実行されます。ご想像のとおり、まだまだ時間がかかると思いますが、最初の100万件を1分以内で実行しました。だから私はそれが実行可能な範囲内にあると確信しています。

幸運を ：）

アップデート2

あなたからの別のコメントの後、私は自分が間違っていることを理解し、それを修正しようとしました。

from itertools import product, combinations_with_replacement, permutations
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_dice = dice-top
    n_sets = len(set([p for p in permutations(range(n_dice)+['x']*top)]))
    n_count = dict((n, n_sets*len([p for p in combinations_with_replacement(range(1,n+1,1),n_dice)])) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

ご想像のとおり、これはかなりの惨事であり、正しい答えを与えることすらできません。これは数学者に任せるつもりだと思います。これを解決する私の方法は単純に次のようになるからです。

def calc_ways1(dice, sides, top, total):
    return len([p for p in product(xrange(1,sides+1,1),repeat=dice) if sum(sorted(p)[-top:]) == total])

これはエレガントな1行のソリューションであり、正しい答えを提供しますcalc_ways1(5,6,3,15)が、問題には永遠にかかりますcalc_ways1(20,12,10,70)。

とにかく、私の愚かな考えではなく、数学は確かにこれを進める方法のようです。

于 2012-12-12T11:15:33.997 に答える