2
$\begingroup$

Given a summation like

$$\sum_{1 \leq i_1 < i_2 < \dotsc < i_k \leq n} f(i_1, i_2, \dotsc , i_k)$$

how can the lists of indices be enumerated?

For example, if $n=4$ then the possible lists of indices are

k=1: {1}, {2}, {3}, {4}
k=2: {1,2}, {1,3}, {2,3}, {2,4}, {3,4}
k=3: {1,2,3}, {1,2,4}, {2,3,4}
k=4: {1,2,3,4}

It doesn't matter in what order the lists appear in, and it doesn't matter if they are separated by $k$, i.e., this function could give the lists of indices for a given $k$ value, or list all lists for $k=1 \dotsc n$ (the 14 in the example) in arbitrary order.

This is similar to the question Sequential Subsets of a list except that in the example given there, given a list

{1, 2, 3, 4}

the output is

{1}, {2}, {3}, {4}, 
{1,2}, {2,3}, {3,4},
{1,2,3}, {2,3,4},
{1,2,3,4}

(in some order) and in this case, we additionally need

{1,3}, {2,4}, {1,2,4}

to appear in the output.

$\endgroup$
  • 1
    $\begingroup$ Is this what you're after: f @@@ Rest@Subsets[Range[4]] // Total? $\endgroup$ – Kuba Apr 23 '14 at 21:11
  • $\begingroup$ Yes, Subsets works perfectly here, thanks. Unfortunately I was looking for something that works for larger $n$, for example Subsets[100] exceeds machine integer size. You can do something like ask only for the $m$th subset of a particular size, but this is very slow. There may not be a feasible solution for large $n$. $\endgroup$ – J M Apr 23 '14 at 21:52
1
$\begingroup$

For the special case you can work with all the terms:

f @@@ Rest@Subsets[Range[4]] // Total

but if the range is too high and you don't need all the terms you can proceed with functions from Combinatorica package\subsets

Needs["Combinatorica`"]
NextKSubset[Range@100, {1, 2, 15, 17}]
{1, 2, 15, 18}
$\endgroup$
1
$\begingroup$

There are only two ways to enumerate a set of something that I know:

  • Return the full set, or
  • Provide a function that, given an element of the set, returns the next element, under some ordering.

For your problem, that first way is given by a built-in function Subsets:

Subsets[Range[4],{2}]

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

while the second way can be implemented directly:

nextIndex[l_, n_] := Module[{k = n, i = Length[l]},
  While[And[l[[i]] == k, i >= 1], i = i - 1; k = k - 1];
  If[i == 0, False,
   Join[Take[l, i - 1], l[[i]] + Range[Length[l] - i + 1]]]]

nextIndex[{1, 4, 5}, 5]

{2, 3, 4}

NestList[nextIndex[#, 4] &, Range[2], 6]

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, False}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.