On Wed, Feb 04, 2009 at 10:15:26PM -0800, Ben Pfaff wrote: > Here's an explanation. ... > Notably, these trivial cases include all values of W for N = 1. > > Now consider the remaining, nontrivial cases, that is, N > 1 and > 1 <= W <= N*(N+1)/2. In this case, apply the following identity: > > S(N,W) = S(N-1, W) + S(N-1, W-N). > > The first term on the right hand is the number of subsets that do > not include N that sum to at least W; the second term is the > number of subsets that do include N that sum to at least W. > > Then we repeatedly apply the identity to the result, reducing the > value of N by 1 each time until we reach N=1. Some expansions > yield trivial cases, e.g. if W - N <= 0 (in which case we add a > 2**N term to the final result) or if W is greater than the new N.
Simple and clever. I think you should publish this. I'm not surprised it hasn't been used in statistical software before. Most people in the field of non-parametric statistics don't think about algorithms from discrete math. It's a good result, especially for a sleepless night's work. -Jason _______________________________________________ pspp-dev mailing list [email protected] http://lists.gnu.org/mailman/listinfo/pspp-dev
