Python - самый эффективный способ генерации комбинаций больших множеств по критериям?

Question

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

Например, предположим, что у меня есть коллекция списков, которые представляют распределения в портфель с учетом минимального и максимального процента от общего размера портфеля для каждого инструмента:

"US Bonds" = {0.10,0.15,0.20,0.25,0.30} 
"US Equities" = {0.25, 0.30, 0.35, 0.40, 0.45, 0.50} 
"European Bonds" = {0.10, 0.15, 0.20} 
"European Equities = {0.20,0.25,0.30,0.35,0.40,0.45,0.50} 
... 
"Cash" = {0.0, 0.05, 0.10, 0.15,...0.95} 

Мой список, актив, таким образом, выглядит так:

[In] 
Asset 

[Out] 
[[0.1, 0.15, 0.2, 0.25, 0.30], 
[0.25, 0.30,0.35, 0.40, 0.45, 0.50], 
[0.1, 0.15, 0.2], 
[0.20, 0.25, 0.30,0.35, 0.40, 0.45, 0.50] 
... 
[0.0, 0.05, 0.1, 0.15, 0.2, 0.25,...0.95]] 

что является наиболее эффективным способом для получения всех возможных портфелей с учетом критериев, что сумма каждой комбинации приборов должна быть = 1?

На данный момент я создаю список 'портфелей' следующим образом:

portfolios = [item for item in itertools.product(*asset) if np.isclose(sum(item),1)] 

(нб, 'np.isclose' заботиться о фанки Fp арифметики).

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

Есть несколько вопросов, касающихся наилучшего исполнения для различных комбинаций, но я не видел никаких граничных условий.

Answer 1

(Примечание: код доступен по адресу: http://lpaste.net/145213)

Прежде всего, будет представлять проценты как целые значения, чтобы избежать плавающей запятой ошибок округления.

Во-вторых, самый эффективный метод будет использовать ограничение, чтобы не смотреть на портфели, которые не могут удовлетворить ограничение == 1.

Петля вы хотите писать будет работать так:

def portfolios(): 
    for us_bonds in [ 10, 15, 20, 25, 30 ]: 
    if us_bonds > 100: break 
    for us_equaties in [ 25, 30, 35, 40, 45, 50 ]: 
     if us_bonds + us_equaties > 100: break 
     for euro_bonds in [ 10, 15, 20 ]: 
     if us_bonds + us_equaties + euro_bonds > 100: break 
     for euro_equaties in [ 20, 25, 30, 35, 40, 45, 50 ]: 
      if us_bonds + us_equaties + euro_bonds + euro_equaties > 100: break 
      cash = 100 - (us_bonds + us_equaties + euro_bonds + euro_equaties) 
      yield [us_bonds, us_equaties, euro_bonds, euro_equaties, cash] 

Это определяет генератор, который вы можете использовать в for цикле, как это:

for x in portfolios(): print x 

Этот подход является эффективным, поскольку он избегает построения портфелей, которые превышают ограничение == 100. Заметим также, что мы воспользовались тем фактом, что процент «Наличных» в принципе может быть любым - так что он просто занимает разницу между 100 процентами и суммой других категорий инвестиций.

Следующая функция обобщает эту петлю для произвольного числа инвестиционных категорий:

def gen_portfolio(categories): 
    n = len(categories) 
    tarr = [0] * (n+1) 
    parr = [0] * (n+1) 
    karr = [0] * (n+1) 
    marr = [ len(c) for c in categories ] 
    i = 0 
    while True: 
    while True: 
     if i < n: 
     p = categories[i][ karr[i] ] 
     t = tarr[i] + p 
     if t <= 100: 
      parr[i] = p 
      tarr[i+1] = t 
      i += 1 
      karr[i] = 0 
      continue 
     else: 
      break     # backup 
     else: 
     parr[n] = 100 - tarr[n] # set the Cash percentage 
     yield parr[:]    # yield a copy of the array parr 
     break 
    # backup 
    while True: 
     if i > 0: 
     i -= 1 
     karr[i] += 1 
     if karr[i] < marr[i]: break 
     else: 
     return # done! 

def portfolios2(): 
    cats = [ [ 10, 15, 20, 25, 30 ], [ 25, 30, 35, 40, 45, 50 ], [ 10, 15, 20 ], [ 20, 25, 30, 35, 40, 45, 50 ] ] 
    return gen_portfolio(cats) 

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

def compareTest(): 
    ports1 = [ x for x in portfolios() ] 
    ports2 = [ x for x in portfolios2() ] 
    print "ports1 length:", len(ports1) 
    print "ports2 length:", len(ports2) 
    for x in ports1: 
    if x not in ports2: print "not in ports2:", x 
    for x in ports2: 
    if x not in ports1: print "not in ports1:", x 

Update

Вот пример, демонстрирующий разницу между этим методом и itertools.product.

Предположим, что существует 10 категорий инвестиций, а проценты - [90,91, .., 99] для каждой категории. Вложенные циклы с заявлениями перерыв будет действовать следующим образом:

start the loop: for p1 in [90,91,..,99] 

    set p1 = 90 
    p1 < 100 so continue 

    start the loop: for p2 in [90,91,..,99] 
    set p2 = 90 
    p1 + p2 > 100, so break out of the p2 loop 

    set p1 = 91 

    p1 < 100 so continue 
    start the loop: for p2 in [90,91,..,99] 
    set p2 = 90 
    p1 + p2 > 100, so break out of the p2 loop 
    set p1 = 92 
    ... 

Таким образом, вложенные циклы с заявлениями перерыв выглядит только в 10 случаях - p1 = 90, 91, .., 99 и p2 = 90. p2 никогда не получает любой более 90, и он никогда не пытается присваивать что-либо p3, p4, ..., p10.

С другой стороны, itertools.product будет генерировать все 100 случаев, а затем вы должны отфильтровать те комбинации, сумма которых равна 100.>

Для некоторых входов itertools.product может быть быстрее, так как это написанный на C, но он не делает никаких обрезков дел, основанных на сумме текущих выборов.