# Count number of sublists with a total not greater than a given max

Suppose I have a list of positive integers:

data={1, 1, 2, 3, 3, 3, 5, 5, 5, 7, 7, 8, 8, 9, 10, 10, 12, 16, 23}


I want to count the number of subsets up to length t (including an empty set) whose total doesn't exceed the value t.

The naive approach would be:

sumZaehl[t_, data_] :=
Length@Select[Total /@ Subsets[data, t], # <= t &]


But this would not work for larger list, because of the rapidly increasing number of subsets. I have an iterative method which works for larger list too:

sumZaehlIter[t_, data_] :=
Module[{n = Length[data], v, d, i, j},
For[i = 0, i <= t, i++, v[i] = 1];
For[i = 1, i <= n, i++,
d = data[[i]];
For[j = t, j >= d, j--,
v[j] = v[j] + v[j - d];
]];
v[t]]


Is there a functional way to realize this?

-
I figure that the sublists with a total not greater than 3 are following six: {{},{1},{2},{3},{1,1},{1,2}}. Yet both your sumZaehlIter[3,data] and Leonid's v[3,data] return 10. What are the other four sublists with a total not greater than 3? – DavidC Mar 6 '12 at 3:29
@David, I think (with multiplicities of some elements), there are two additional occurences of {3} and one additional occurence for each of {1} and {2,1}. – kglr Mar 6 '12 at 7:57
@kguler Interesting. So it has nothing to do with the order of the elements within a sublist? – DavidC Mar 6 '12 at 10:14
@David, yes; so the complete collection is {{},{1},{1},{2},{3},{3},{3},{1,1},{1,2},{1,2}}. – kglr Mar 6 '12 at 10:44

This is not really the same algorithm, but

ClearAll[v];
v[t_, data_] :=
Block[{v},
v[_?Negative, _] := 0;
v[_, 0] := 1;
v[tl_, n_] := v[tl, n] =
v[tl - data[[n]], n - 1] + v[tl, n - 1];
v[t, Length[data]]
];


You may need to increase the \$RecursionLimit for larger lists.

-
the iterative Module works quite well but I'm interested in functional. With the "naive" way I get errors "Subset::toomany and "must be a machine integer". Why "a machine integer" – Peter Breitfeld Mar 5 '12 at 20:38
@Peter Your iterative algorithm uses a lot of mutable state. While you probably can achieve the same with the functional constructs, I suspect that the direct translation of it into functional would be either inefficient or resulting in a thin functional facade over the essentially procedural core. The algorithm I posted above has the same underlying idea as yours, but IMO is a functional version of it (although not a direct translation), using recursion and memoization. A similar situation happens e.g. with the longest common sequence algorithm. – Leonid Shifrin Mar 5 '12 at 21:03
That's beautiful. +1 – Mr.Wizard Mar 6 '12 at 8:10
Nice solution! +1 – Pillsy Mar 6 '12 at 16:08
@Pillsy, Mr.Wizard Thanks! – Leonid Shifrin Mar 6 '12 at 17:11

Ah, came across this from the "related" bar, time for a necro :-}

Here's a direct and fast one-liner:

numSST[t_, s_] := Block[{p = Normal[Times @@ (1 + x^s) + O[x]^(t + 1)], x = 1}, p];

-
@ciao...I really enjoyed this one-liner... – ubpdqn Aug 23 '15 at 11:25
Nice use of O[]. ;) – J. M. Aug 23 '15 at 11:33