Эффективный алгоритм бинания элемента (itertools/numpy)

Question

Я думаю, что это общая проблема комбинаторики, но я не могу найти имя для нее или какой-либо материал об этом. Я делаю это в Python и numpy, но если для этого существует быстрый матричный метод, я могу, вероятно, перевести.

В принципе, учитывая п пунктов, мне нужно создать все способы, чтобы положить их в м бункеров. Например, разбиение 4 предметов на 3 ящика даст что-то вроде [(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...]. Это продукт с фиксированным итогом.

Реализация этого с помощью itertools проста.

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)) 

К сожалению, я думаю, что последующие вычисления в цикле будут неэффективными. Работа с этим как массивом 2D numpy будет быстрее позже, но я не могу найти эффективный способ построения массива с этим. Я мог бы перебирать результат ifilter, строя список возможностей и использовать его для построения массива, но это кажется огромной тратой.

Я предполагаю, что лучший способ сделать это - построить все «numpy way», но я не уверен, как это сделать. Быстрая реализация продукта в stackoverflow: Using numpy to build an array of all combinations of two arrays. Я предполагаю, что вы можете изменить это только для вывода продуктов с правильной суммой. Размер массива должен быть ((m-1) + n) выбирать n, так как существуют границы m-1 bin.

Любые идеи? Тесты очень ценятся, но не требуются.

Answer 1

На основе рекурсии C (n, k) = C (n - 1, k) + C (n - 1, k - 1), memoized, с использованием операций 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) 

Время в секундах (20, 5):

0.0129251480103 

Answer 2

Возможно, существует более быстрый способ использования нескольких различных трюков в numpy. numpy.indicies - это то, где вы хотите начать. Это по существу эквивалент itertools.product, как только вы объедините его с rollaxis. Ответ Свена Марнаха in this question - отличный пример этого (в последнем примере есть небольшая ошибка, но это то, что вы хотите использовать. Это должно быть numpy.indices((len(some_list) + 1), * some_length...)

Однако, для чего-то вроде этого, вероятно, будет более читаемый с использованием itertools.

numpy.fromiter немного быстрее, чем прямое преобразование вещей в список, особенно если вы укажете ему количество элементов в итераторе. Главное преимущество заключается в том, что используется значительно меньше памяти, что может быть очень полезно в случае больших итераторов.

Вот некоторые примеры с использованием как numpy.indices трюка и различными способами преобразования итератора в Numpy массива:

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) 

Что касается времени:

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 

Вы не заметите, что ни один из они особенно быстры.

Вы используете алгоритм грубой силы (генерируете все возможные комбинации, а затем фильтруете их), и я просто копирую его в примере на основе numpy.

Возможно, существует гораздо более эффективный способ сделать это! Тем не менее, я никоим образом не являюсь специалистом в области CS или математики, поэтому я не знаю, есть ли известный алгоритм для этого, не создавая сначала все возможные комбинации ...

Удачи, во всяком случае !