18
$\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?

Improve this question
$\endgroup$
4
  • $\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
    Commented Mar 6, 2012 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
    Commented Mar 6, 2012 at 7:57
  • $\begingroup$ @kguler Interesting. So it has nothing to do with the order of the elements within a sublist? $\endgroup$
    – DavidC
    Commented Mar 6, 2012 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
    Commented Mar 6, 2012 at 10:44

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Mar 5, 2012 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
    Commented Mar 5, 2012 at 21:03
  • $\begingroup$ That's beautiful. +1 $\endgroup$
    – Mr.Wizard
    Commented Mar 6, 2012 at 8:10
  • $\begingroup$ Nice solution! +1 $\endgroup$
    – Pillsy
    Commented Mar 6, 2012 at 16:08
  • $\begingroup$ @Pillsy, Mr.Wizard Thanks! $\endgroup$
    – Leonid Shifrin
    Commented Mar 6, 2012 at 17:11
6
$\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];
Improve this answer
$\endgroup$
2
  • $\begingroup$ @ciao...I really enjoyed this one-liner... $\endgroup$
    – ubpdqn
    Commented Aug 23, 2015 at 11:25
  • $\begingroup$ Nice use of O[]. ;) $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Aug 23, 2015 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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