Перестановки с ограничением суммы


Я создал следующую функцию, что дает перестановочные комбинации из n элементов с ограничения/правила. В этом состоят на создание таблицы данных с все комбинации цифр от 0 до N, что суммы Н.

Функция

import pandas as pd
import itertools
import numpy as np

def combinations_permuted(n_elm):
    items = list(range(0,n_elm+1,1))
    combinations = pd.DataFrame(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.combinations_with_replacement(items, n_elm)))))
    comb_permuted = pd.DataFrame()
    for index, combination in combinations.iterrows():
        comb_permuted=comb_permuted.append(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.permutations(combination.tolist(), n_elm)))))

    return(comb_permuted.drop_duplicates().as_matrix())

Пример

array([[0, 0, 3],
       [0, 3, 0],
       [3, 0, 0],
       [0, 1, 2],
       [0, 2, 1],
       [1, 0, 2],
       [1, 2, 0],
       [2, 0, 1],
       [2, 1, 0],
       [1, 1, 1]], dtype=int64)

Проблема в том, что занимает много времени, когда n_elm это "большой", например 9. Я думаю, что этот код можно улучшить с точки зрения времени работы.

Может быть, путем замены for петли с map функция.

Любая помощь, чтобы получить его?



Комментарии
1 ответ


def combinations_permuted(n_elm):

ИМО n (как используется в описании код в вопрос) является более читабельным, чем n_elm.


    items = list(range(0,n_elm+1,1))

1 по умолчанию шаг, и range не так уж непонятные функции, содержание программиста будет интересно, что range(0, n+1) делает.


    combinations = pd.DataFrame(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.combinations_with_replacement(items, n_elm)))))
comb_permuted = pd.DataFrame()
for index, combination in combinations.iterrows():
comb_permuted=comb_permuted.append(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.permutations(combination.tolist(), n_elm)))))

return(comb_permuted.drop_duplicates().as_matrix())


Есть две вещи, которые звучат колокола предупреждение:


  1. comb_permuted=comb_permuted.append. Документация для таблицы данных.добавить говорит


    Итерационно при добавлении строк в таблицу данных может быть более ресурсоемким, чем один объединить. Лучшее решение-добавить эти строки в список, а затем объединить список с исходными данными таблицы все сразу.

  2. drop_duplicates(). Что говорит о том, что процесс генерации делает больше работы, которую он должен получить.

Поцелуй подходом было бы заменить combinations_with_replacement, permutations, drop_duplicates цепь с itertools.product. Это намного быстрее n = 3, но уже медленнее n = 5 (потому что все равно делать больше работы, что ему необходимо, и фильтрация).

Эффективный подход-делать только ту работу, которая необходима. Быстрый и грязный реализации (т. е. пожалуйста, уберите ее перед использованием) вычисляет для n = 6 в меньше время чем это берет исходный код для расчета n = 3:

def combinations_recursive_inner(n, buf, gaps, sum, accum):
if gaps == 0:
accum.append(list(buf))
else:
for x in range(0, n+1):
if sum + x + (gaps - 1) * n < n: continue
if sum + x > n: break
combinations_recursive_inner(n, buf + [x], gaps - 1, sum + x, accum)

def combinations_recursive(n):
accum = []
combinations_recursive_inner(n, [], n, 0, accum)
return pd.DataFrame(accum).as_matrix()

Онлайн-тест и бенчмарк

1
ответ дан 21 марта 2018 в 04:03 Источник Поделиться