Продукт массива с заданным динамическим числом аргументов c - PullRequest
Новая
       35

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

0 голосов
/ 30 апреля 2020

У меня есть функция, которая делает продукт массива: 

arrayProduct(l1,l2,l3) = [[a, b, c] |
    a := l1[_]
    b := l2[_]
    c := l3[_]
]

Если у меня есть три массива, определенных следующим образом: 

animals1 = ["hippo", "giraffe"]
animals2 = ["lion", "zebra"]
animals3 = ["deer", "bear"]

Тогда вывод arrayProduct(animals1, animals2, animals3) будет: 

[["hippo","lion","deer"],["hippo","lion","bear"],["hippo","zebra","deer"],["hippo","zebra","bear"],["giraffe","lion","deer"],["giraffe","lion","bear"],["giraffe","zebra","deer"],["giraffe","zebra","bear"]]

Если я могу гарантировать, что входные данные всегда будут списками, я могу создать функцию, которая будет делать то же самое, за исключением того, что она может принимать динамическое c число списков в качестве ввода вместо просто 3?

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

[["hippo", "giraffe"], ["lion", "zebra"], ["deer", "bear"], ["ostrich", "flamingo"]]

Любое понимание решения с любым из подходов будет приветствоваться.

Ответы [ 2 ]

2 голосов
/ 30 апреля 2020

Не существует известного способа вычисления произвольного N-стороннего перекрестного произведения в Re go без встроенного.

Почему что-то не может быть написано на языке, может быть сложно объяснить, потому что это составляет пробный эскиз. Нам нужно привести аргумент, что в Re go нет политики, которая вычисляет N-стороннее перекрестное произведение. Формальные доказательства выразительности / сложности не были разработаны, поэтому лучшее, что мы можем сделать, это попытаться сформулировать, почему это может быть невозможно.

Для кросс-продукта N-way это сводится к факту что Re go гарантирует завершение для всех политик на всех входах, а для этого ограничивает насколько глубоко может быть вложенная итерация. В вашем примере (используя some и отступ для ясности) у вас есть 3 вложенных цикла с индексами i, j, k. 

arrayProduct(l1,l2,l3) = [[a, b, c] |
    some i
        a := l1[i]
        some j
            b := l2[j]
            some k
                c := l3[k]
]

Для реализации N-стороннего перекрестного произведения arrayProduct([l1, l2, ..., ln]) вам понадобится что-то эквивалентное N вложенным циклам: 

# NOT valid Rego
arrayProduct([l1,l2,...,ln]) = [[a, b, ..., n] |
    some i1
        a := l1[i1]
        some i2
            b := l2[i2]
              ...
                    n := ln[in]
]

, где важно, степень вложенной итерации N зависит от входных данных.

Чтобы гарантировать завершение, Re go ограничивает степень вложенной итерации в политике. Вы можете вкладывать итерацию только столько раз, сколько some (или более правильных переменных) появляется в вашей политике. Это аналогично SQL, ограничивающему количество JOIN'ов теми, которые появляются в запросах и представлениях определений.

Поскольку степень вложенности, необходимая для N-двунаправленного перекрестного произведения, равна N, а N может быть больше, чем число some с в политике, нет способа реализовать N-двунаправленное перекрестное произведение. product.

В качестве контраста, количество ключей или значений, которые повторяются внутри любого l oop CAN и обычно ДОЛЖНЫ зависеть от ввода. Это количество циклов, которое не может зависеть от ввода.

1 голос
/ 30 апреля 2020

Невозможно вычислить n-арное произведение списков / массивов (или наборов или объектов) в Re go без добавления встроенной функции.

В описанном выше сценарии, предоставляя Dynami c число массивов в качестве входных данных для функции будет эквивалентно передаче массива массивов (как вы упомянули в конце): 

arrayProduct([arr1, arr2, ..., arrN])

Это работает, за исключением случая, когда мы пытаемся реализовать arrayProduct мы застряли, потому что Re go не разрешает рекурсию, и итерация происходит только тогда, когда вы вводите переменную в ссылку. В исходном примере l1[_] является ссылкой на элементы в первом списке, а _ является уникальной переменной, ссылающейся на индексы массива в этом списке.

OPA / Re go оценивает это выражение по поиск назначений для каждого _, которые удовлетворяют запросу. «Проблема» в том, что для этого требуется одна переменная для каждого списка во входных данных. Если длина массива массивов неизвестна, нам понадобится бесконечное число переменных.

Если вам действительно нужна n-арная функция произведения, я бы предложил вам реализовать пользовательскую встроенную функцию на данный момент.

...