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

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

В принципе, учитывая n элементов, мне нужно создать все способы поместить их в m бункеров. Например, разбиение 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: Использование numpy для создания массива всех комбинаций из двух массивов. Я предполагаю, что вы можете изменить это только для вывода продуктов с правильной суммой. Размер массива должен быть ((m-1) + n) выбирать n, так как существуют границы m-1 bin.

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

Ответ 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

Ответ 2

Вероятно, существует более быстрый способ использования нескольких разных трюков в numpy. numpy.indicies - это то, где вы хотите начать. Это, по сути, эквивалент itertools.product, как только вы объедините его с rollaxis. Ответ Sven Marnach в этом вопросе является отличным примером этого (там небольшая ошибка в его последнем примере, однако, это то, что вы хотите использовать. Оно должно быть 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 или математиком человеком, поэтому я не знаю, есть ли известный алгоритм для этого, не генерируя все возможные комбинации в первую очередь...

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