Efektywne poz binning algorytm (itertools/numpy)

Question

myślę, że jest to wspólny problem kombinatoryki, ale nie wydaje się znaleźć nazwę dla niego lub jakichkolwiek materiałów na jego temat. Robię to w Pythonie i numpy, ale jeśli jest na to szybka metoda macierzowa, prawdopodobnie mogę to przetłumaczyć.

Zasadniczo, biorąc pod uwagę n przedmiotów, muszę wygenerować wszystkie sposoby, aby umieścić je w m pojemników. Jako przykład binning 4 pozycji na 3 kosze dałby coś podobnego [(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...]. To jest produkt o stałej wartości całkowitej.

Realizacja tego z itertools jest proste.

import itertools 

def fixed_total_product(bins, num_items): 
""" Return iterator of all item binning possibilities. """ 
return itertools.ifilter(lambda combo: sum(combo) == num_items, 
         itertools.product(xrange(num_items + 1), repeat=bins)) 

Niestety, myślę, że wykonanie kolejnych obliczeń w pętlach będzie nieefektywne. Praca z tym jako tablicą 2D numpy byłaby szybsza później, ale nie mogę wymyślić wydajnego sposobu na zbudowanie tablicy z tym. Mógłbym powtórzyć wynik ifiltera, budując listę możliwości i użyć tego do skonstruowania tablicy, ale wydaje się to ogromnym marnotrawstwem.

Zgaduję, że najlepszym sposobem, aby to zrobić jest budowanie wszystkiego „na drogę” numpy, ale nie jestem pewien, jak to zrobić. Istnieje szybka implementacja produktu na stackoverflow: Using numpy to build an array of all combinations of two arrays. Zgaduję, że możesz to zmienić tylko do produktów wyjściowych z odpowiednią sumą. Rozmiar tablicy powinien wynosić ((m-1) + n) wybrać n, ponieważ istnieją granice bin m-1.

Wszelkie pomysły? Benchmarks bardzo doceniane, ale nie wymagane.

Answer 1

Na podstawie rekurencji C (n, k) = C (n - 1, k) + C (n - 1, k - 1), zapamiętane, przy użyciu operacji numpy.

import numpy as np 

def binnings(n, k, cache={}): 
    if n == 0: 
     return np.zeros((1, k)) 
    if k == 0: 
     return np.empty((0, 0)) 
    args = (n, k) 
    if args in cache: 
     return cache[args] 
    a = binnings(n - 1, k, cache) 
    a1 = a + (np.arange(k) == 0) 
    b = binnings(n, k - 1, cache) 
    b1 = np.hstack((np.zeros((b.shape[0], 1)), b)) 
    result = np.vstack((a1, b1)) 
    cache[args] = result 
    return result 

if __name__ == '__main__': 
    import timeit 
    print timeit.timeit('binnings(20, 5, {})', setup='from __main__ import binnings', number=1) 

czas w sekundach (20, 5):

0.0129251480103 

Answer 2

Prawdopodobnie jest to szybszy sposób za pomocą kilku różnych sztuczek w numpy. numpy.indicies to miejsce, od którego chcesz zacząć. Jest to w istocie odpowiednikiem itertools.product, gdy połączyć je z rollaxis. Sven Marnach za odpowiedź in this question jest doskonałym tego przykładem (jest drobny błąd w swoim ostatnim przykładzie jednak, do czego chcesz używać. Powinno być numpy.indices((len(some_list) + 1), * some_length...)

jednak na coś takiego, to może być bardziej czytelny przy użyciu itertools.

numpy.fromiter jest nieco szybszy niż konwersja jawnie rzeczy na listę, szczególnie jeśli podasz liczbę elementów w iteratorze. Główną zaletą jest to, że wykorzystuje znacznie mniej pamięci, co może być bardzo pomocne w przypadku dużych iteratorów.

Oto przykłady wykorzystujące zarówno numpy.indices trik i na różne sposoby przekształcania iterator do numpy tablicy:

import itertools 
import numpy as np 
import scipy.special 


def fixed_total_product(bins, num_items): 
    return itertools.ifilter(lambda combo: sum(combo) == num_items, 
      itertools.product(xrange(num_items + 1), repeat=bins)) 

def fixed_total_product_fromiter(bins, num_items): 
    size = scipy.special.binom(bins - 1 + num_items, num_items) 
    combinations = fixed_total_product(bins, num_items) 
    indicies = (idx for row in combinations for idx in row) 
    arr = np.fromiter(indicies, count=bins * int(size), dtype=np.int) 
    return arr.reshape(-1, bins) 

def fixed_total_product_fromlist(bins, num_items): 
    return np.array(list(fixed_total_product(bins, num_items)), dtype=np.int) 

def fixed_total_product_numpy(bins, num_items): 
    arr = np.rollaxis(np.indices((num_items + 1,) * bins), 0, bins + 1) 
    arr = arr.reshape(-1, bins) 
    arr = np.arange(num_items + 1)[arr] 
    sums = arr.sum(axis=1) 
    return arr[sums == num_items] 

m, n = 5, 20 

if __name__ == '__main__': 
    import timeit 
    list_time = timeit.timeit('fixed_total_product_fromlist(m, n)', 
      setup='from __main__ import fixed_total_product_fromlist, m, n', 
      number=1) 
    iter_time = timeit.timeit('fixed_total_product_fromiter(m, n)', 
      setup='from __main__ import fixed_total_product_fromiter, m, n', 
      number=1) 
    numpy_time = timeit.timeit('fixed_total_product_numpy(m, n)', 
      setup='from __main__ import fixed_total_product_numpy, m, n', 
      number=1) 

    print 'All combinations of {0} items drawn from a set of {1} items...'.format(m,n) 
    print ' Converting to a list and then an array: {0} sec'.format(list_time) 
    print ' Using fromiter: {0} sec'.format(iter_time) 
    print ' Using numpy.indices: {0} sec'.format(numpy_time) 

chodzi o termin:

All combinations of 5 items drawn from a set of 20 items... 
    Converting to a list and then an array: 2.75901389122 sec 
    Using fromiter: 2.10619592667 sec 
    Using numpy.indices: 1.44955015182 sec 

Zauważysz, że żaden z są szczególnie szybkie.

Używasz algorytmu brute-force (generuj wszystkie możliwe kombinacje, a następnie filtruj je), a ja po prostu kopiuję je w przykładzie opartym na numpy.

Jest prawdopodobnie o wiele bardziej skuteczny sposób na zrobienie tego! Nie jestem jednak w żadnym razie osobą z CS lub matematyki, więc nie wiem, czy istnieje dobrze znany algorytm, który nie generuje wszystkich możliwych kombinacji ...

Powodzenia, w każdym razie !