Message Boards Message Boards

0
|
6261 Views
|
10 Replies
|
6 Total Likes
View groups...
Share
Share this post:

How to find all multi-indices satisfying given contraints?

Posted 10 years ago

Hey there,

First, in case someone isn't familiar with multi-indices, they are essentially lists of non-negative integers, e.g. $\alpha = (\alpha_1,\ldots,\alpha_n).$ Further, denote $\left| \alpha \right|_1 = \sum_{i=1}^n \left|\alpha_i\right|$.

What I would like is some efficient way of finding all multi-indices for a given $n$ satisfying

$$ a \leq \left| \alpha \right|_1 \leq b, $$

with the additional constraint that $\alpha_i > 0$ for each $1 \leq i \leq n$. The integers $a$ and $b$ are of course given.

More specifically, I need to sum over all such multi-indices (passing each as an argument to a function), but that's simple enough once I have a list of the multi-indices.

-Jonatan

POSTED BY: Jonatan Lehtonen
10 Replies

You could just have a1 go from 1 to b-n+1, a2 from 1 to (b-n+1)-a1, a3 from 1 to (b-n+1)-(a1+a2), etc.

One can use Reduce to find all actual multiindex sets, but that 's overkill. Likewise, could look at exponents in the expansion of (1+a1+a2+...+an)^(b-a)*(a1+...+an)^a. Again, overkill.

POSTED BY: Daniel Lichtblau

Just table it out

With[{b= ...., n = ...},
allowedInd = Table[{a1,a2,a3,...}, {a1,1,b-n+1},{a2, 1, b-n+2-a1},{a3, 1, b-n+3-a1-a2},...]
]

and use it afterwards. Be careful to formulate correct Table-iterators.

Another simple way is to include If-statements into the generic summand term, giving 0 if the multi-index is not allowed to contribute.

POSTED BY: Udo Krause
POSTED BY: Jonatan Lehtonen

Lower conditions as well as the whole job can be done by brute force up to a certain n

In[41]:= With[{b = 7, n = 5, a = 1},
 If[a < 0 || n < 0 || b < 1 || b - n < a, Print["You will get the empty set!"]];
 If[a < n, Print["Your conditions run empty on lower boundary!"]];
 Union[Flatten[
    DeleteMissing[
     Table[If[a <= Plus @@ {a1, a2, a3, a4, a5} <= b, 
       X[a1, a2, a3, a4, a5], Missing[]],
      {a1, 1, b - 1}, {a2, 1, b - 1}, {a3, 1, b - 1}, {a4, 1, 
       b - 1}, {a5, 1, b - 1}], n]]] /. X -> List
 ]

During evaluation of In[41]:= Your conditions run empty on lower boundary!

Out[41]= {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 2}, {1, 1, 1, 1, 3}, {1, 1, 1, 2, 1}, {1, 1, 1, 2, 2}, {1, 1, 1, 3, 1},
          {1, 1, 2, 1, 1}, {1, 1, 2, 1, 2}, {1, 1, 2, 2, 1}, {1, 1, 3, 1, 1}, {1, 2, 1, 1, 1}, {1, 2, 1, 1, 2}, 
          {1, 2, 1, 2, 1}, {1, 2, 2, 1, 1}, {1, 3, 1, 1, 1}, {2, 1, 1, 1, 1}, {2, 1, 1, 1, 2}, {2, 1, 1, 2, 1}, 
          {2, 1, 2, 1, 1}, {2, 2, 1, 1, 1}, {3, 1, 1, 1, 1}}

if you want multi-indices disregarding the order, it is simply

In[42]:= With[{b = 7, n = 5, a = 1},
 If[a < 0 || n < 0 || b < 1 || b - n < a,  Print["You will get the empty set!"]];
 If[a < n, Print["Your conditions run empty on lower boundary!"]];
 Union[Sort /@ 
    Flatten[DeleteMissing[
      Table[If[a <= Plus @@ {a1, a2, a3, a4, a5} <= b, 
        X[a1, a2, a3, a4, a5], Missing[]],
       {a1, 1, b - 1}, {a2, 1, b - 1}, {a3, 1, b - 1}, {a4, 1, 
        b - 1}, {a5, 1, b - 1}], n]]] /. X -> List
 ]

During evaluation of In[42]:= Your conditions run empty on lower boundary!

Out[42]= {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 2}, {1, 1, 1, 1, 3}, {1, 1, 1, 2, 2}}

this last thing brings you to an efficient way to do it: Start with the trivial allowed lower bound multiindex {1,1,1,..., Max[1,a-n+1]}, raise the last position until the limit b is reached ({1,1,1,...,b-n+1}) now distribute the IntegerPartitions/@ Range[Max[1,a-n+1],b-n+1-Max[1,a-n+1]] over the trivial allowed lower bound multiindex, with other words

In[51]:= With[{b = 7, n = 5, a = 1},
 If[a < 0 || n < 0 || b < 1 || b - n < a, Print["You will get the empty set!"]];
 If[a < n, Print["Your conditions run empty on lower boundary!"]];
 Join[{{1, 1, 1, 1, Max[1, a - n + 1]}},
  {1, 1, 1, 1, Max[1, a - n + 1]} + PadLeft[#, n] & /@ 
   Flatten[IntegerPartitions /@ 
     Range[Max[1, a - n + 1], b - n + 1 - Max[1, a - n + 1]], 1]]
 ]

During evaluation of In[51]:= Your conditions run empty on lower boundary!

Out[51]= {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 2}, {1, 1, 1, 1, 3}, {1, 1, 1, 2, 2}}

if they are needed with respect to order, the result must be shuffled back to un-order.

Check for errors please, and find possibly other, even more efficient ways to do it!

POSTED BY: Udo Krause
POSTED BY: Jonatan Lehtonen
POSTED BY: Udo Krause

An interesting addition, but in my work computing the multi-indices will never actually be the bottleneck, since both the computation time and memory usage for the remainder of my program is exponential in $b$.

POSTED BY: Jonatan Lehtonen

This might be what you have in mind.

indicesFromLowToHigh[l_, h_, n_, var_] := Module[
  {vars = Array[var, n]},
  Table[{var[j], 1, h - n + j - Sum[var[k], {k, j - 1}]}, {j, n}]
  ]

Example:

indicesFromLowToHigh[2, 7, 3, x]

Out[361]= {{x[1], 1, 5}, {x[2], 1, 6 - x[1]}, {x[3], 1, 
  7 - x[1] - x[2]}}

For actual use as a sequence of iterators one would have something like Sequence@@indicesFromLowToHigh[...].

POSTED BY: Daniel Lichtblau
POSTED BY: Udo Krause

Have you tried Subsets (if you want the indices in order) or Tuples (for the more general case)? You may then have to add a shift.

The most common case is to pick k indices from n in ascending order. Say 3 indices from 5:

Subsets[Range[5], {3}]

Giving:

{{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}}
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract