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.

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?

share|improve this question
    
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? –  David Carraher 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}. –  kguler Mar 6 '12 at 7:57
    
@kguler Interesting. So it has nothing to do with the order of the elements within a sublist? –  David Carraher 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}}. –  kguler Mar 6 '12 at 10:44
add comment

1 Answer 1

up vote 7 down vote accepted

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.

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

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.