Biorąc pod uwagę listę liczb całkowitych e.g.

l = [3, 5, 8, 13]

I liczbę całkowitą e.g.

m = 13

Policz liczbę kombinacji całkowitych, które mają sumę = m np.

combinations = len([[8, 5], [5, 8], [13], [3, 5, 5], [5, 5, 3], [3, 5, 3], ...])

Dla małych wartości Mogę użyć tej rekurencji (Fibonacci-podobna liniowa relacja nawrotu):

def RecursiveCount(m, integers):
    count = 0
    if m < 0:
        return 0
    if m == 0:
        return 1
    for i in integers:
        count += RecursiveCount(m-i, integers)
    return count

Ale dla większych L i M, jest to powolne i zaproponowało, aby wykorzystać dynamiczne programowanie do zapamiętania już rozwiązań kombinacji w celu zmniejszenia połączeń rekurencyjnych. Niestety, nie jestem w stanie tego wdrożyć. Próbowałem tego czytać, ale nie pomogłem https://bio.informatik.uni-jena.de/wp/wp-content/uploads/2014/09/book_handout_3.pdf

Edytuj: Wynik edukacyjny byłby największy, gdyby był w stanie wdrożyć go przy użyciu dynamicznego programowania

1
Benni 4 czerwiec 2018, 13:25

3 odpowiedzi

Najlepsza odpowiedź

Prosty czas wyszukiwania jest to O(n * k), gdzie n jest sumą i k jest liczbą liczb całkowitych na liście. Przestrzeń wyszukiwania może być ograniczona do O(max(list)), ale dla wygody możemy użyć O(n).

Kod Pythona:

def f(n, nums):
  m = [0 for i in range(n + 1)]

  for s in range(min(nums), n + 1):
    for c in nums:
      if c == s:
        m[s] += 1
      if c < s:
        m[s] += m[s - c]

  return m[n]

Wyjście:

nums = (3, 5, 8, 13, 15, 20)
m = 200

t0 = time.time()
x = num_seq_sum(m, nums) # jdehesa's code
t1 = time.time()

print(x, t1-t0) # 233354368688517335733 4.085544586181641

t0 = time.time()
x = f(m, nums)
t1 = time.time()
print(x, t1-t0) # 233354368688517335733 0.0004315376281738281

t0 = time.time()
x = RecursiveCount(m, nums) # using @functools.lru_cache()
t1 = time.time()
print(x, t1-t0) # 233354368688517335733 0.0006241798400878906
2
גלעד ברקן 4 czerwiec 2018, 23:13

To rozwiązanie nie korzysta z dynamicznego programowania, ale jest znacznie szybszy:

import math
from functools import reduce

def num_seq_sum(m, nums):
    if m == 0:
        return 1
    # Avoid repeated numbers
    nums = list(set(nums))
    # Begin with no numbers picked
    base = [0] * len(nums)
    return sum(_seqs_sum_rec(m, nums, base, 0))

def _seqs_sum_rec(m, nums, current, i):
    if i >= len(nums):
        raise StopIteration
    # Try without adding current number, add next numbers
    yield from _seqs_sum_rec(m, nums, current, i + 1)
    # Try adding current number
    n = nums[i]
    # While we can fit more copies of current number
    while m > n:
        current[i] += 1
        m -= n
        yield from _seqs_sum_rec(m, nums, current, i + 1)
    # If we can fit exactly one more
    if m == n:
        current[i] += 1
        # Number of permutations of the current combination
        yield _num_permutations(current)
    # Undo additions for parent call
    current[i] = 0

def _num_permutations(comb):
    return math.factorial(sum(comb)) // reduce(lambda a, b: a * b, (math.factorial(c) for c in comb), 1)

nums = [3, 5, 8, 13]
m = 13

print(RecursiveCount(m, nums) == num_seq_sum(m, nums))
# True

Mały test wydajności:

nums = [1, 3, 5, 8, 10, 15]
m = 30

%timeit RecursiveCount(m, nums)
# 1.48 s ± 6.86 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit num_seq_sum(m, nums)
# 4.77 ms ± 85.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1
jdehesa 4 czerwiec 2018, 14:15

Możesz łatwo dodać zapamiętanie, dodając {x0}} Dekorator do funkcji rekurencyjnej.

@functools.lru_cache()
def RecursiveCount(m, integers):
    ...

Spowoduje to automatycznie pamięć wyników dla niektórych parametrów i sprawdzić, czy najpierw pamięć podręczna przed ponownym wywołaniem funkcji znacznie znacznie zmniejszając liczbę połączeń, a zatem środowisko wykonawcze. Wymaga to jednak wszystkie parametry do zniesienia, tj. Musiałbyś przejść integers jako tuple.

Przykład dla RecursiveCount(20, tuple(range(1, 10)))): Wynik: 518,145; Wywołanie funkcji bez wspomnienia: 4,672,513; Z zapamiętaniem: 29.

(Jeśli jest to na ćwiczenie w DP, prawdopodobnie nie jest to opcja, ale w przeciwnym razie działa dobrze w praktyce.)

3
tobias_k 4 czerwiec 2018, 10:51