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

Question

Я думаю, что это общая проблема комбинаторики, но я не могу найти название для нее или какой-либо материал об этом. Я делаю это на 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))

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

Я предполагаю, что лучший способ сделать это - построить все "тупым путем", но я не уверен, как это сделать. Существует быстрое внедрение продукта в stackru: использование numpy для создания массива всех комбинаций из двух массивов. Я предполагаю, что вы можете изменить это только для вывода продуктов с правильной суммой. Размер массива должен быть ((m-1) + n), выберите n, так как есть границы m-1 бина.

Есть идеи? Тесты высоко ценятся, но не обязательны.

Answer 1

Исходя из рекурсии C(n, k) = C(n - 1, k) + C(n - 1, k - 1), запоминается, используя 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, Ответ Свена Марнача на этот вопрос является прекрасным примером этого (однако в его последнем примере есть небольшая ошибка, которую вы хотите использовать. Это должно быть 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

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

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

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

В любом случае, удачи!