Как я могу избежать Nested For-l oop для выбора комбинации? - PullRequest
Новая
       8

Как я могу избежать Nested For-l oop для выбора комбинации?

0 голосов
/ 24 января 2020

Например, есть M атрибутов a_1, ..., a_M для выбора и каждый атрибут имеет N вариантов выбора .
Проблема заключается в поиск целых комбинаций из N ^ M вариантов выбора.
Используя вложенный for-l oop, псевдокод подобен приведенному ниже. 

# length of a_1, ..., a_M is N for each.
for c_1 in a_1:
  for c_2 in a_2:
    ...
      for c_M in a_M:
         evaluate(c_1, c_2, ..., c_M)

Однако этот крайний вложенный for-l oop выглядит очень плохо, и я не хочу писать оператор for M раз.
Кроме того, если мы не знаем число атрибутов для рассмотрения, мы даже не можем использовать этот код.
Существуют ли более простые и элегантные способы, как описано выше?

1 Ответ

1 голос
/ 24 января 2020

Похоже, ваша проблема связана с декартовым произведением. Обратите внимание, что размер результата (количество комбинаций) равен L1*L2*L3..*LM, где Li - количество вариантов выбора для ai

. Вы можете реализовать его с помощью рекурсии или использовать соответствующую библиотеку, если она доступна

Python пример: 

import itertools
l = [['a', 'b'], [1, 2, 3], [False, True]]
print([list(a) for a in itertools.product(*l)])

>>> [['a', 1, False], ['a', 1, True], ['a', 2, False], ['a', 2, True], 
     ['a', 3, False], ['a', 3, True], ['b', 1, False], ['b', 1, True], 
     ['b', 2, False], ['b', 2, True], ['b', 3, False], ['b', 3, True]]

Пример рекурсивной и итеративной реализации: 

def product_rec(a, fromindex, res):
    if fromindex == len(a):
        print(res)
        return
    for x in a[fromindex]:
        product_rec(a, fromindex+1, res+[x])

def product_iter(a):
    NN = 1
    for x in a:
        NN *=  len(x)  #number of combinations
    b = [[0]*len(a) for i in range(NN)]
    N = NN
    M = 1
    for k in range(len(a)):  
        N //=  len(a[k])
        c = 0
        for l in range(M):
            for i in range(len(a[k])):
                for j in range(N):
                    b[c][k] = a[k][i]
                    c += 1
        M *= len(a[k])
    print(b)

l = [['a', 'b'], [1, 2, 3], [False, True]]

product_rec(l, 0, [])
product_iter(l)
...