# Ordered indices of a multiple product or sum

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.

-
Is this what you're after: f @@@ Rest@Subsets[Range[4]] // Total? – Kuba Apr 23 '14 at 21:11
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$. – John Apr 23 '14 at 21:52

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}

-

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}

-