Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
1  
Is this what you're after: f @@@ Rest@Subsets[Range[4]] // Total? –  Kuba Apr 23 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 at 21:52

2 Answers 2

up vote 0 down vote accepted

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}
share|improve this answer

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}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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