17
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – DavidC Mar 6 '12 at 3:29
  • $\begingroup$ @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}. $\endgroup$ – kglr Mar 6 '12 at 7:57
  • $\begingroup$ @kguler Interesting. So it has nothing to do with the order of the elements within a sublist? $\endgroup$ – DavidC Mar 6 '12 at 10:14
  • $\begingroup$ @David, yes; so the complete collection is {{},{1},{1},{2},{3},{3},{3},{1,1},{1,2},{1,2}}. $\endgroup$ – kglr Mar 6 '12 at 10:44
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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" $\endgroup$ – Peter Breitfeld Mar 5 '12 at 20:38
  • $\begingroup$ @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. $\endgroup$ – Leonid Shifrin Mar 5 '12 at 21:03
  • $\begingroup$ That's beautiful. +1 $\endgroup$ – Mr.Wizard Mar 6 '12 at 8:10
  • $\begingroup$ Nice solution! +1 $\endgroup$ – Pillsy Mar 6 '12 at 16:08
  • $\begingroup$ @Pillsy, Mr.Wizard Thanks! $\endgroup$ – Leonid Shifrin Mar 6 '12 at 17:11
5
$\begingroup$

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];
$\endgroup$
  • $\begingroup$ @ciao...I really enjoyed this one-liner... $\endgroup$ – ubpdqn Aug 23 '15 at 11:25
  • $\begingroup$ Nice use of O[]. ;) $\endgroup$ – J. M. will be back soon Aug 23 '15 at 11:33

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.