Связанные суммы с Nest

Aug 20 2020

Я хочу вычислить такую ​​цепную сумму $$ C_m = \sum\limits_{i_1=1}^N \;\sum\limits_{i_2=i_1+1}^N \;\sum\limits_{i_3=i_2+1}^N \cdots \;\sum\limits_{i_m=i_{m-1}+1}^N A_{i_1}A_{i_2}A_{i_3}\cdots A_{i_m} $$ Например, когда $m=3$, это становится $$ C_3 = \sum\limits_{i=1}^N \;\sum\limits_{j=i+1}^N \;\sum\limits_{k=j+1}^N A_i A_j A_k $$ Конечно дело в том, что я хочу $m$оставаться неуказанным в алгоритме. Теперь я знаю, как реализовать это, вручную составляя списки итераторов (например, с помощью Tuples) и применяя Sumк ним. Но для меня это больше похоже на взлом, чем на элегантный код.

Поскольку я всегда стараюсь сделать свой код как можно более элегантным, я рассматриваю это как хорошую возможность для изучения. Одна из концепций, которые мне всегда трудно понять (но я бы хотел освоить), - это использование Nestи Fold. Эту сумму можно рассматривать как вложенную в себя функцию.$$ C_m = \sum\limits_{i_1=1}^N A_{i_1} \left[ \;\sum\limits_{i_2=i_1+1}^N A_{i_2} \left[ \;\sum\limits_{i_3=i_2+1}^N A_{i_3} \left[ \cdots\vphantom{\sum\limits_{i_3=i_2+1}^N} \right]\right]\right] $$Я ожидал Nestбыть идеальным кандидатом. Я немного пробовал, но лучшее, что я мог придумать, это

f[g_,j_] := Sum[g[k]A[k], {k,j+1,n}]
F[x_] := f[x,#]&

c[m_] := f[Nest[F,1&,m-1],0]

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

c[m_] := Sum[
  Nest[ Function[var,Sum[var[k]A[k],{k,#+1,5}]&], 1&, m-1][l] A[l]
, {l,1,n}]

с необходимостью использования Functionи &.

Итак, вот мой вопрос: есть ли более аккуратный способ достичь этой связанной суммы с помощью Nest? Если нет, может быть, с помощью какой- Foldлибо другой функциональной конструкции?

Ответы

3 march Aug 20 2020 at 21:21

Tableделает это автоматически. Вы должны уметь адаптировать следующий код:

f[m_, n_] := Sum[
   Product[A[i[j]], {j, 1, m}] // Evaluate, 
   Sequence @@ Prepend[Table[{i[j], i[j - 1] + 1, n}, {j, 2, m}], {i[1], 1, n}] // Evaluate
  ]

Таким образом

f[2, 3]
(* A[1] A[2] + A[1] A[3] + A[2] A[3] *)

и

f[3, 5]
(* A[1] A[2] A[3] + A[1] A[2] A[4] + A[1] A[3] A[4] + A[2] A[3] A[4] + A[1] A[2] A[5] + A[1] A[3] A[5] + A[2] A[3] A[5] + A[1] A[4] A[5] + A[2] A[4] A[5] + A[3] A[4] A[5] *)

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

f2[n_, m_] := Times @@@ Map[A, Subsets[Range[m], {n}], {2}] // Total
f2[3, 5]
(* A[1] A[2] A[3] + A[1] A[2] A[4] + A[1] A[3] A[4] + A[2] A[3] A[4] + A[1] A[2] A[5] + A[1] A[3] A[5] + A[2] A[3] A[5] + A[1] A[4] A[5] + A[2] A[4] A[5] + A[3] A[4] A[5] *)

и

f[3, 5] - f2[3, 5]
(* 0 *)

Или же

f3[n_, m_] := Sum[Times @@ A /@ is, {is, Subsets[Range[m], {n}]}]
SteffenJaeschke Aug 22 2020 at 18:48

«Nest [f, expr, n] дает выражение, в котором f применяется к expr n раз».

Nest принимает функцию, выражение и n положительных целых чисел.

Не больше, не меньше.

Nest как-то устарело.

Его заменяет Composition.

Compositionявляется математическим элементарным членом Nest, полученным от с .

В документации Composition есть пример суммы:

Composition[HoldForm, Plus] @@ Range[20]
___
\!\(
TagBox[
RowBox[{"1", "+", "2", "+", "3", "+", "4", "+", "5", "+", "6", "+", 
    "7", "+", "8", "+", "9", "+", "10", "+", "11", "+", "12", "+", 
    "13", "+", "14", "+", "15", "+", "16", "+", "17", "+", "18", "+", 
    "19", "+", "20"}],
HoldForm]\)

Это показывает, что Sum и Nest довольно разные.

Sumполучается из Plusвышеуказанного способа. На странице документации Plusпоказаны альтернативы Sum.

Для создания сложных продуктов Mathematica предлагает встроенные функции Product. На Nestстранице документации нет ни строчки с, Productни наоборот.

Что это означает для вашего вопроса? Теперь сначала ничего. Но это сильный намек.

В то время Nestкак итеративно с n, константа "times" в позиции третьего аргумента Productне требует x ", но требует итератора i с началом и концом. Это то, что представляют ваши слагаемые. Я принимаю примеры на странице документации, поскольку Productони далеки от легкий или много специализированный.

Вот несколько хороших примеров и методов, как сделать это более эффективным:

∑𝑖=2𝑁cos𝜃𝑖cos𝜃′𝑖∏𝑗=𝑖+1𝑀sin𝜃𝑗𝜃′𝑗

    NSum[Cos[θ[[i]]] Cos[Θp[[i]]] Product[    Sin[θ[[j]]] Sin[θp[[j]]], {j, i + 1, d - 1}], {i, 2,    d - 1}]


f[M_, n_] := Reverse[Table[Cos[θ[i]] Cos[θ'[i]], {i, 2, n}]].PadLeft[FoldList[
Sin[θ[M - #2] θ'[M - #2]] # &, Sin[θ[M] θ'[M]], Range[M - 3]], Max[n - 1, 0], 1]

Этот вопрос уже касается суммы или продукта с исключениями .

Сумма более важна для получения закрытых формуляров, как в этом примере:

Sum[Product[i^2, {i, 1, n}], {i, 1, n}]
n (n!)^2

n = 4;
Times @@ Flatten@Table[f[a[i] - a[j]], {i, 1, n - 1}, {j, i + 1, n}]

или же

With[{n = 6}, Times @@ f /@ Subtract @@@ Subsets[Array[a, n], {2}]]

может быть выполнено с помощью итератора или списка. Итератору необходимо, чтобы список коэффициентов был уже определен, и он выполняет итерацию линейным образом. В более современных версиях Mathematica вторая версия должна быть быстрее в большинстве случаев.

Формула используют разные операторы @, @@и @@@которые отличаются от Composition @*.

Это высоко оцененный ответ о сканировании, карте и применении . Этот ответ объясняет некоторые различия между Composition и Apply . Эти ответы гораздо глубже затрагивают связанные с этим темы: формы операторов v10s для чего они нужны?

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

ClearAll[list1, list2, a, b, c, x, y, z, f]
list1 = {a, b, c}
list2 = {x, y, z}
___
Map[Map[f[#1, #2] &, list1] &, list2]
__
list2
___
Map[Function[x, Map[f[#1, x] &, list1]], list2]
___
list2

Но желаемый результат таков

Outer[f, list1, list2]
(*
  {{f[a, x], f[a, y], f[a, z]}, 
   {f[b, x], f[b, y], f[b, z]}, 
   {f[c, x], f[c, y], f[c, z]}}
*)

Map[Function[p2, Map[Function[p1, f[p1, p2]], list1]], list2]

(* {{f [a, x], f [b, x], f [c, x]}, {f [a, y], f [b, y], f [c, y]}, { f [a, z], f [b, z], f [c, z]}} *)

Если f в not listable, это тоже можно записать так:

Distribute[f[{a, b, c}, {x, y, z}], List]
(*
  {{f[a, x], f[b, x], f[c, x]}, 
   {f[a, y], f[b, y], f[c, y]}, 
   {f[a, z], f[b, z], f[c, z]}}
*)

Следующая альтернатива -

Кортежи [{{a, b, c}, {x, y, z}}] ( {{a, x}, {a, y}, {a, z}, {b, x}, {b, y }, {b, z}, {c, x}, {c, y}, {c, z}} )

Apply[f, Tuples[{{a, b, c}, {x, y, z}}], {1}]

( {f [a, x], f [a, y], f [a, z], f [b, x], f [b, y], f [b, z], f [c, x] , f [c, y], f [c, z]} )

А это, в свою очередь, позволяет добиться желаемого Nest:

Гнездо [f, #, 1] & / @ Кортежи [{{a, b, c}, {x, y, z}}] ( {f [{a, x}], f [{a, y}] , f [{a, z}], f [{b, x}], f [{b, y}], f [{b, z}], f [{c, x}], f [{c , y}], f [{c, z}]} )

Этот вопрос о вложенном-свернутом-есть-там-расширении-для-более-чем-2-аргументов относится к главе 5.5.3. Ограничение функции складывания двумя аргументами является ложным по отношению к онлайн-книге Леонида Шифрина и пример с тремя слотами:

multiFoldList[f_, start_, args__List] := 
 FoldList[f @@ Prepend[#2, #] &, start, {args}\[Transpose]] 
____
multiFoldList[#1 (1 + #2) - #3 &, 1000, {.01, .02, .03}, {100, 200, 
  300}]
___
{1000, 910., 728.2, 450.046}

Это очень особенные, но они помогают, и расширения уже включены.

А пока, наконец, я хотел бы сослаться на эту обзорную статью.

Альтернативы-процедурным-циклам-и-повторению-спискам-в-математике /

который включает несколько примеров использования Fold и Nest и сравнивает это в различных ситуациях с альтернативными встроенными модулями. Все это довольно приятно и предлагает более глубокое понимание того, Nestчто можно и что нельзя делать. Я сравниваю встроенный Nestс другими встроенными модулями и комбинациями и Compositions.

Поищите в документации Mathematica Iterator, чтобы получить его как лучшее определение входного значения n и некоторое объяснение выбора парадигмы Mathematica по этому поводу.

В документации Mathematica есть два определения Expression: одно для ячеек и одно для интерпретатора языка Wolfram Language. Итак, такое руководство по поиску во входах, посвященных полезности WolframAlpha

Взгляните на FixedPoint - встроенную программу, исторически сгруппированную с Nest и предназначенную для поколения пользователей Mathematica в качестве ограничивающей встроенной программы Nest для бесконечных итераций, приложений. Знаменитый учебник «Многократное применение функций».

определяет диапазоны индексов, с которыми может справиться система Mathematica на основе языка Wolfram Language.

Вот чего не хватает Nest и им подобным, а у Prodcut есть.