1

私が書いたアルゴリズムが多項式時間で動作するかどうかを判断しようとしています.

def combo(list, size):
    if size == 0 or not list:                            # order doesn't matter
        return [list[:0]]                                # xyz == yzx
    else:
        result = []
        for i in range(0, (len(list) - size) + 1):       # iff enough left
            pick = list[i:i+1]
            rest = list[i+1:]                            # drop [:i] part
            for x in combo(rest, size - 1):
                result.append(pick + x)
        return result
4

3 に答える 3

1

「k-combinations」のアルゴリズムがあります。n 個のアイテムが与えられた場合、k 個のアイテムを選択し、順序を無関係として扱います。古代から、予想される組み合わせの数はわかっています。

    n!
-----------
(n - k)! k!

特定の n (たとえば、10) に対して、その式は、k が n の半分 (5) に等しいときに最大化されます。n または k のいずれかが極値に近づくにつれて、組み合わせの数ははるかに少なくなります。

少し再編成して単純化することで、コードを書き直してcombos()、最悪の場合でも の呼び出し数が組み合わせの数とほぼ同じになるようにすることができます。興味深いことに、呼び出しの数と組み合わせの数は、きれいに対称的な逆関係にあります。

最も重要なことは、両方が上に示した最悪の場合の式によって制限されることです。それは事実上O()、あなたが求めている境界です。しかし、正確ではないかもしれません。なぜなら、書き直されたコードは、同じ結果を生成するにもかかわらず、コードよりも少ないサブルーチン呼び出しを行うからです。以下の例の短絡ロジックは、余分な呼び出しを防ぎ、最悪のケースの引数が正常に動作できるようにします。

その式が最悪の場合の境界である場合、アルゴリズムは多項式時間で実行されますか? 私はそのような問題の専門家というよりも直感的ですが、答えはノーだと思います。最悪のケースは whenk = n / 2であり、次の単純化が得られます。分母は非常に急速に大きくなりますが、チャック・ノリスの分子の成長率と比較すると見劣りします。

      n!
-------------
(n/2)! (n/2)!

# For example, when n = 40.

       product(1..40)             product(      21..40)   # Eat my dust, Homer!
-----------------------------  =  ---------------------
product(1..20) product(1..20)     product(1..20       )   # Doh!

# Q.E.D.

n と k の多くの値の経験的な説明:

from itertools import combinations
from math import factorial

n_calls = 0

def combos(vals, size):
    # Track the number of calls.
    global n_calls
    n_calls += 1

    # Basically your algorithm, but simplified
    # and written as a generator.
    for i in range(0, len(vals) - size + 1):
        v = vals[i]
        if size == 1:
            yield [v]
        else:
            for c in combos(vals[i+1:], size - 1):
                yield [v] + c

def expected_n(n, k):
    # The mathematical formula for expected N of k-combinations.
    return factorial(n) / ( factorial(n - k) * factorial(k) )

def main():
    global n_calls

    # Run through a bunch of values for n and k.
    max_n = 15
    for n in range(1, max_n + 1):
        # Worst case is when k is half of n.
        worst_case = expected_n(n, n // 2)

        for k in range(1, n + 1):
            # Get the combos and count the calls.
            n_calls = 0
            vs = list(range(n))
            cs = list(combos(vs, k))

            # Our result agrees with:
            #   - itertools.combinations
            #   - the math
            #   - the worst-case analysis
            assert cs      == list(list(c) for c in combinations(vs, k))
            assert len(cs) == expected_n(n, k)
            assert n_calls <= worst_case
            assert len(cs) <= worst_case

            # Inspect the numbers for one value of n.
            if n == max_n:
                print [n, k, len(cs), n_calls]

main()

出力：

[15, 1, 15, 1]
[15, 2, 105, 15]
[15, 3, 455, 105]
[15, 4, 1365, 455]
[15, 5, 3003, 1365]
[15, 6, 5005, 3003]
[15, 7, 6435, 5005]
[15, 8, 6435, 6435]
[15, 9, 5005, 6435]
[15, 10, 3003, 5005]
[15, 11, 1365, 3003]
[15, 12, 455, 1365]
[15, 13, 105, 455]
[15, 14, 15, 105]
[15, 15, 1, 15]
于 2013-06-18T05:40:18.680 に答える