Code covered by the BSD License  

Highlights from
nsumk

2.0

2.0 | 1 rating Rate this file 13 Downloads (last 30 days) File Size: 1.67 KB File ID: #28340

nsumk

by

 

30 Jul 2010 (Updated )

Returns the number and listing of n-tuples of non-negative integers adding up to k.

| Watch this File

File Information
Description

Little more than syntactic sugar for nchoosek, this small but surprisingly controversial function returns the number of (ordered) n-tuples of non-negative integers adding up to k, and if supplied a second argument, a listing of them. As an alternative to downloading, just cut and paste the following:

 m = nchoosek(k+n-1,n-1);
 dividers = [zeros(m,1),nchoosek((1:(k+n-1))',n-1),ones(m,1)*(k+n)];
  x = diff(dividers,1,2)-1;
 
It has been noted with some passion that this it is possible to achieve the same result using partitions.m, a more general function posted on Matlab Central. Indeed nsumk(n,k) returns the same result as sortrows(partitions(k, ones(1,n))). For small problems the latter is probably no more than 10x slower than using nchoosek. For large problems the performance of nsumk is substantially better (but only because we desire a special ordering).

These observations may be more relevant to others than this author, and no effort has been made to optimize nsumk (or for that matter nchoosek). See vchoosek.m for a faster .mex implementation of nchoosek.

Acknowledgements

Partitions Of An Integer, Unique Random Permutations, and V Choose K inspired this file.

This file inspired Laplace.M.

MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (29)
18 Aug 2010 Rob Campbell

I have no use for this function but the above discussion is wonderful.

15 Aug 2010 Peter Cotton

Thanks Jan,
I'll update the description
Peter

12 Aug 2010 Sean

Ha ha ha! I thoroughly enjoyed this very entertaining discussion!

06 Aug 2010 Jan Simon

VCHOOSEK is a Mex, which is > factor 100 faster than NCHOOSEK:
http://www.mathworks.com/matlabcentral/fileexchange/26190

You do not have to check twice, if n and k are scalars:
if ~isscalar(n) || ~isscalar(k); error(...); end
m = nchoosek(k+n-1,n-1);
if nargout == 2
dividers = [zeros(m,1), vchoosek((1:(k+n-1))',n-1),ones(m,1)*(k+n)];
x = diff(dividers,1,2)-1;
end
Congratulation for the great discussion! Jan

04 Aug 2010 Peter Cotton

Hi Andy,

Apologies for my tardiness in replying and your suggestions are well intentioned. Small quibbles over timing are mere definitional (I need the right order - thus included sortrows) but potentially larger philosophical differences relate to the stability and maintainability of code (of which nsumk.m is a very tiny piece). I generally refrain from giving others style or programming advice but using a great honking general function might not always be the best decision when it can be accomplished either by three lines of code, or a teeny weeny function such as nsumk.m ... not that I knowingly made a conscious decision given my ignorance.

No justification is required for reducing code complexity but I leave the rants to others. I suggest googling "premature generalization", for example.

Regards,

Peter

04 Aug 2010 Andy

On my machine, the reasonable domain for nsumk appears to be n<=14 and k<=13, or n=15 and n<=11. (The case n=14, k=14 did not return after a long time, so I gave up on it. The output for the case n=15, k=13 would be nearly as large as n=14, k=14, so I don't think my machine can handle this one either. I didn't bother with higher n because I don't have much time to fiddle with this right now. But of course higher n with low k will still be quick.)

For this domain, of course, you only ever need to calculate the lists once. I wrote a function nsumk2 that works on this domain, and is probably nearly optimal in terms of speed:

n=15;
k=12;
tic;
[m,x] = nsumk(n,k);
toc
clear x % don't want to run out of memory
tic;
y = nsumk2(15,12);
toc

% displays:
Elapsed time is 368.176743 seconds.
Elapsed time is 1.464170 seconds.

I can maybe make this slightly faster, and I think I can extend the domain a little bit (to get bigger output like with n=14, k=14; not just trivially with, say, n=16, k=4). But I don't have time to work on this, and I won't for a few weeks.

04 Aug 2010 Andy

I will respond to your points in order:

1. You're not duplicating the functionality of nchoosek, you are extending it (if only by a few lines). But you are duplicating a small part of the functionality of partitions.

2. John found your documentation confusing, which it was.

3. It's not an issue of being upset. I don't have any particular need for your code, so I really don't care if you use nchoosek. But you stated that speed was a goal, and I suggested two ways to improve the speed: rewrite nchoosek, and use MEX files. You don't seem to like either of these ideas, for whatever reasons that you have not shared.

4. nsumk is not a waste of space, nor did I ever say it was. I said I see no justification for using it instead of partitions unless the speed is further optimized.

5. I don't know when 6x changed to 10x. On my machine, nsumk was 4-6x faster than partitions. For example:

n=13;
k=6;
tic;
[m,x]=nsumk(n,k);
t1=toc
tic;
y = partitions(k, ones(1,n));
t2=toc
isequal(sortrows(x),sortrows(y))
t2/t1

% displays:
t1 =
0.6823
t2 =
3.3452
ans =
4.9028

In any case, since you seem intent to ignore suggestions for improvement, it's not worth my time to continue commenting on this code.

03 Aug 2010 Peter Cotton

Dear Andy, John,

We seem to be agreeing all of a sudden. How did that happen despite my best efforts?

Andy's view: "I consider the onus to be on you to justify the use of your function over an existing one which provides the same functionality"

Peter's view: I consider the onus to be on myself to justify the use of a function over an existing one which provides the same functionality.

Small difference: Peter thinks said function is called nchoosek, not partitions.m

-+-

John's view: nsumk.m is trivial

Peter's view: nsumk.m is trivial. (hence the original description, "trivial little fella ...")

Small difference: John found it confusing

-+-

Andy's view: nchoosek might not be efficient

Peter's view: nchoosek might not be efficient

Small difference: Peter would like to use it anyway if nobody is too upset.

-+-

Andy's view: nsumk.m is a waste of space

Peter's view: nsumk.m is a waste of space (hence the invitation to cut and paste)

Small difference: Peter thinks it would have been a waste of a lot less space without this discussion

-+-

Andy's view: nsumk.m is not more than 10x faster than partitions

Peter's view: nsumk.m is not more than 10x faster than partitions

Small difference: Peter doesn't necessarily believe in swapping out one function for another just because it is more general and no more than 10x slower.

-+-

Let's get over our small differences

Good night chaps,

Peter

03 Aug 2010 Andy

I think you misunderstood my suggestion. I wasn't saying you should use partitions in combination with MEX files to improve performance. I was suggesting you rewrite nsumk (and nchoosek while you're at it) with MEX files. As I said, it seems the only reason to use nsumk instead of partitions is speed. But nchoosek is hardly optimized for speed itself, and, as you have said, nsumk is little more than a three-line wrapper for nchoosek. For example:

>> edit nchoosek

You can see in the case n < 17 && (k > 3 || n-k < 4) that nchoosek in fact creates all 2^n subsets of the input vector v, and then selects those rows which sum to k. There is also a variable which changes size on loop iteration! This is hardly a speed-oriented implementation.

I find it surprising that when speed is your stated goal, you seem very against exploring ways to try to optimize the speed your function.

"Perhaps you might explain that a 10x difference is unlikely to materially alter the domain of application.

Best of luck with that!"

I have stated my reasons why I think the speed increase does not materially alter the domain of application. Feel free to provide evidence or arguments to the contrary. So far you've given one example of inputs n=15, k=11 for which your function returns an answer and partitions does not. However, I haven't been able to duplicate this result.

I should also add that I, and not John, have been the one suggesting that there ought to be some justification for using nsumk over partitions, which provides the same functionality (and much more) and has been around for several years. I consider the onus to be on you to justify the use of your function over an existing one which provides the same functionality. Speed is a good justification, but, as I've said, I don't know the application for which this small speed increase has been valuable. And if speed is really an issue, then there are obvious next steps for improvement.

03 Aug 2010 John D'Errico

Peter - I find it insulting that you think my entire point of view is that this trivial toy infringes on my own work.

The fact is as I have repeatedly stated - that your code failed to satisfy its own documentation. If it actually worked as described, I would have gladly said it was good.

03 Aug 2010 Peter Cotton

Andy,

I am not telling anyone to use one thing over another - the onus evidently lies with John. I do remain mildly bemused given the fervent evangelizing of partitions.m (I did not start this discussion) and the reasons why I should use it in my present work are not becoming any clearer despite your well meaning intervention. Given a choice between:

(a) Using three lines of Matlab involving nchoosek.m (which is thoroughly tested, supported, and may even benefit from performance improvements over time)

(b) Introduce another dependency by using a lengthy unsupported function "partitions.m" (perhaps in combination with .mex files to compensate for performance).

I will go for the former. Just my personal preference however and fans of partitions.m are welcome to take it up with Mathworks. Your arguments provide an equally persuasive case for implementing nchoosek.m itself using partitions.m, or even removing nchoosek altogether. Perhaps you might explain that a 10x difference is unlikely to materially alter the domain of application.

Best of luck with that!

Peter

03 Aug 2010 Andy

"A skeptic might suggest that your confusion (and complaints about 0 appearing in the solution, or numbers greater than n for that matter) arose not from lack of clarity on my part but from your assumption that this function should follow the same syntax as your own (though as it turns out, you were not even using your own function appropriately - thanks to Andy for noticing)."

Well, that's a somewhat misleading summary of the argument. John at no point said that the same syntax used with his partitions function should give the same result. Rather, he was referring to the syntax used for nchoosek, which your original help section said that nsumk was somewhat related to. (The nature of that relationship was precisely what you were asked to make more explicit.) The complaints about 0 (or 4, or 5) appearing in the output were unrelated to partitions. These complaints were because your original help file didn't say in full detail how it treated vector inputs. (More specifically, it didn't say explicitly that only the length of the vector input mattered.)

Also, I'd like to reiterate a point I made earlier. It seems that the only argument for nsumk over partitions is speed. If this is the case, have you explored a MEX option to see if it would be made even faster? I would think a performance increase would help in two scenarios:
1) the speed increase is significant enough to allow for higher inputs to return in reasonable time, or
2) the function is going to be run over and over again, and the savings of a few seconds per call will translate to minutes overall.

First, a speed increase of five times really is irrelevant when the size of your output grows super-exponentially in the size of your input. It would take a much greater speed increase to move to n=16 or higher. (I should mention that although your included speed tests indicate that nsumk can handle n=15 and partitions can't, in fact neither function returns with n=15 and k=11 on my machine, so I can't confirm the speed difference.)

Second, I can't think of any reason you would need to run nsumk repeatedly with the same arguments, since the output will never change.

On the other hand, if you could increase the speed by a factor of 100 or 1000, you might be able to use n=16, and that would be a real argument for nsumk.

03 Aug 2010 Peter Cotton

Dear John,

We were starting to miss you.

I'm afraid that despite your protestations some readers might be forgiven for thinking that you launched into a rather bizarre attack on this tiny piece of code without so much as reading the one line description, which I repeat here one more time:

"n-tuples of non-negative integers adding up to k"

A skeptic might suggest that your confusion (and complaints about 0 appearing in the solution, or numbers greater than n for that matter) arose not from lack of clarity on my part but from your assumption that this function should follow the same syntax as your own (though as it turns out, you were not even using your own function appropriately - thanks to Andy for noticing).

I give you the benefit of doubt and will assume that you are merely protecting the best interests of matlab users against a proliferation of inherently inferior special cases of partitions.m. Yet since this special case is a 3-liner, perhaps you might turn your efforts to its application within special cases of partitions.m, just in case there are users who don't consider performance factors of five, ten or worse irrelevant.

Regards,

Peter

03 Aug 2010 John D'Errico

No, my reaction was to poor help, that failed to even remotely describe what the code does. It was a reaction to a lack of an H1 line, and to your own unwillingness to accept that your code may have any problem at all.

03 Aug 2010 Peter Cotton

Andy,

Yes I think those who are interested in smallish combinatorics problems need only partitions.m, but I can't speak for them. This function was intended to provide a canonical listing (for polynomial moment matching and numerical work as it turns out) and finds its way into inner loops (at least in my work). It is here because my meager mind can't memorize diff([zeros(m,1),nchoosek((1:(k+n-1))',n-1),ones(m,1)*(k+n)],1,2)-1) and I hate re-thinking about things like this once every two years!

For this special case I'd suggest users need neither function, and I've updated the description accordingly, summarizing the saner contributions to this discussion including your own. I think John will agree once he recovers from his initial, somewhat territorial reaction. Perhaps he might find time to optimize some special cases in partitions.m, as this discussion demonstrates is clearly possible.

Thanks for you input,

Peter

03 Aug 2010 Andy

You are, of course, correct about the error checking. I can't reproduce that claim of my previous post, so I can only conclude I was in the wrong directory (containing the older version of the code).

But sortrows killing performance? Maybe on the very largest inputs, but not in general:

clear;
clc
a=rand(18564,13); % size of output for n=13, k=6
tic;
a=sortrows(a);
toc
% Elapsed time is 0.015582 seconds.

02 Aug 2010 Peter Cotton

Dear Andy,

You are dead right. Having looked a little closer at partitions.m arguments I see there is more than one way to skin the cat. Thanks for pointing that out.

I am sorry that I have failed to provide you with everything you desire by way of error checking, despite my best intentions. I get

>> [m,x] = nsumk(1:3,2)
??? Error using ==> nsumk at 55
nsumk anticipates scalar k and n

so I can only conclude something got lost in the mail. As to performance, perhaps it is best to fix the part of partitions.m which is 6-8 times slower than it needs to be, but in all seriousness why would one go through this path? This amounts to three lines:

m = nchoosek(k+n-1,n-1);
dividers = [zeros(m,1),nchoosek((1:(k+n-1))',n-1),ones(m,1)*(k+n)];
x = diff(dividers,1,2)-1;

Finally, and most importantly, for my own application I require a fixed, known ordering and sortrows will completely kill performance (as indicated by my timings).

Later,

Peter

02 Aug 2010 Andy

I have some comments relating to this section in the documentation:

% BONUS CLARIFYING MATERIAL:
% Supplied at the behest of John D'Errico (with special thanks):
% * Non-negative means not negative
% * An n-tuple is an ordered list of n elements
% * The result may include integers greater than n (e.g.
% nsumk(1:3,5) contains some 4's and 5's in the answer)
% * The result may include zeros - see i above
% * This function is not the same as nchoosek, though it
% suffers from similar limitations

1. I don't see where John asked for any of this. Also, a lot of this is more confusing than helpful.
2. You don't need to define non-negative.
3. You don't need to define n-tuple. However, you shouldn't be using it in the first place. I'm aware it's the proper mathematical term, but John's point was that MATLAB users may use this function for non-mathematical purposes. You can just call them length n vectors, which, in MATLAB terms, completely and accurately describes them.
4. The third bullet point is extremely confusing. The user is unlikely to know why you all of a sudden (for the first time in the help section) let n be a vector input instead of an integer. (Also, there is no longer any need to take vector input, since you were only doing so before in order to tell your function to return a list instead of a number. Now, using the extra output parameter, the vector input should error.)
5. "see i above"? There's nothing labeled "i" above this statement.
6. "suffers from similar limitations" as nchoosek? What limitations? Don't say this unless you also describe what you mean explicitly.

I would suggest removing this entire block of comments.

And some comments on the updated code:
1. Your inclusion of error-checking has created some unintended consequences that should be fixed. For example, run:

m=nsumk(1:3,2);

m will return as an array (not an integer), which is not intended with a single output argument. And even though you are allowed to call nsumk with vector input this way (which I don't think is intended), you cannot use the form:

[m,x] = nsumk(1:3,2);

This will give an error (correctly).

2. I don't see why it's so hard (600 lines of code?) to get the same functionality with partitions. I believe the following should be equivalent (up to ordering of the rows of the output):

n=13;
k=6;
tic;
[m,x]=nsumk(n,k);
toc
tic;
y = partitions(k, ones(1,n));
toc
isequal(sortrows(x),sortrows(y))

% returns
Elapsed time is 0.668362 seconds.
Elapsed time is 3.698012 seconds.
1

Although nsumk is faster, I don't know that the small increase in speed is worth losing the flexibility of partitions (which can solve many other problems). If speed is really a concern, a MEX approach is likely faster than either of these m-code implementations.

02 Aug 2010 Peter Cotton

Hi Andy,

As I am indifferent to the overloading and error checking, your wish is my command (see update). The second returned argument is the list, the first is the count as you suggest.

I see where you are coming from with your suggestion for x=nsumk(v,k) where v is a vector, but this function is *not* intended as syntactic sugar for partitions.m because we don't benefit from the compression in the Young tableau. Rather, we must produce all *ordered* listings as quickly as possible, which is evidently pretty trivial using nchoosek.m. Going the other way is decidedly more complicated and requires clever code in partitions.m

Because this was not entirely clear to all present, I included an implementation using partitions.m to demonstrate that even though this *looks* like a special case of partitions.m the indisputable mathematical relationship (add one, create partitions, add permutations, subtract one) is not terribly useful:

e.g.: [n,x] = nsumk(13,6) takes 0.24s, whereas going via a list of unordered solutions takes 50s in an admittedly rushed implementation calling partitions.m

Kind regards,

Peter

02 Aug 2010 Andy

I think all John is asking for is that the comments at the beginning look something like this (warning: may not wrap correctly):

% X = NSUMK(N,K) returns the number of length n vectors of nonnegative
% integers whose sum is k.
%
% X = NSUMK(V,K), where V is a vector, is the same as X=NSUMK(LENGTH(V),K).
%
% Example 1: x = nsumk(5,2)
% x =
% 15
%
% Example 2: x = nsumk(1:5,2)
% x =
%
% 0 0 0 0 2
% 0 0 0 1 1
% 0 0 0 2 0
% 0 0 1 0 1
% 0 0 1 1 0
% 0 0 2 0 0
% 0 1 0 0 1
% 0 1 0 1 0
% 0 1 1 0 0
% 0 2 0 0 0
% 1 0 0 0 1
% 1 0 0 1 0
% 1 0 1 0 0
% 1 1 0 0 0
% 2 0 0 0 0
%

I have my own additional comments:
1. As written, there is only error checking for the input n. Try, for example:

x=nsumk(5,'foo');

I consider this unexpected output. It should report an error here.

2. I don't like that x=nsumk(1:5,2) is the same as x=nsumk(2:6,2). I would much prefer functionality as follows:

x=nsumk(n,k): returns number of length n vectors of nonnegative integers summing to k

[x,list]=nsumk(n,k): returns number of length n vectors in x, and returns the vectors in list

x=nsumk(v,k): where v is a vector, returns the number of vectors whose elements come from the set v and sum to k

[x,list] = nsumk(v,k): also returns the vectors

Note how with this usage, nsumk(1:5,2) is not the same as nsumk(2:6,2). It also makes use of the vector input, rather than just using the class of the input as a flag to output the list of vectors rather than the length.

But of course, as stated, this is the functionality of partitions.

01 Aug 2010 Peter Cotton

Dear John,

I hope you are doing very well. I am feeling much refreshed after the weekend and enthusiastic about continuing our task. Admittedly, I am close to forgetting what that was but I believe it involves expanding the help for this six line function to include language prerequisites which tripped you up in the first place: the definition of a non-negative, tuple and so forth. I may be mistaken but in my last post (line wrapping notwithstanding) I had included contiguous comment lines and a most informative lookfor friendly first line. And despite you inference to the contrary I have not broken the function nor have any intention of doing so (I fear it may already have been widely adopted).

Thank you for the well intentioned coding advice and (unlike other people who merely preach) illustrating the dangers by, as you put it, making "wild, unsupported guesses" as to the intention of my code. This is most instructive and the final product will be so much the finer for it. I will await you comments on the previous post and then make a final pass before re-posting. I am confident that this function, though meager in an of itself, may provide a shining example for others on how to provide comments and help.

Kind regards,

Peter

31 Jul 2010 John D'Errico

No! There is no reason to cause help to fail, forcing the user to use type instead! I never suggested that. When did I ever recommend an idea like that?

All that you need to do to enable lookfor is to include ONE MORE LINE, at the very beginning of the help block!!!!!!!!!!! The comment block should be contiguous, to enable both help and lookfor.

Look at EVERY MATLAB function that MathWorks provides. Read the help for lookfor,

As far as the use of your function goes and the help itself, all that I have asked is that you make the help clear, explaining what it does, rather than forcing the user to divine exactly what you mean when you say the word "tuple". While you may feel this is obvious, other users will not have the same background. So make your help clear. Is this really difficult to do? Tell the user what happens when they pass in a vector, don't make them guess that the only piece of information that you take from that vector is the length of the blasted thing!!!!!!!

Good code is friendly to the user. Bad code makes the user make wild, unsupported guesses, and then returns arbitrary results when they lack the ability to read the mind of the author.

30 Jul 2010 Peter Cotton

Dear John,

I see where you got the idea this was supposed to be the same as nchoosek (because it uses the same convention for ordering tuples and has the same limitations). However, this would seem to be in contradiction with the first English line of help, where that elusive definition is hiding. There is also a definition for the vector case:

"listing of n-tuples of non-negative integers adding up to k"

and miraculously, this function performs accordingly:

x = nsumk(1:5,2) returns a list of 5-tuples of non-negative integers, as advertised, 5 being the length of 1:5. The first three happen to be:

0 0 0 0 2
0 0 0 1 1
0 0 0 2 0

All rows sum to 2, also as advertised. (Incidentally it may be possible to create a vector of length 5 in fewer characters than 1:5 but I leave that to others). The overloading is the same as nchoosek. If you want to produce lists I know of no shorter means than

> nchoosek(1:5,2)
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

All that said, I agree with you that the usage "help" is inconsistent and/or foreign. To be precise (in the same style) I could write

x: nchoosek(k+length(n)-1,length(n)-1) x length(n) - listing of non-negative integers with rows summing to k

but I suggest that you would prefer me to break my practice of including the function signature (thereby forcing users to "type nsumk" rather than "help nsumk" as per Mathworks tradition, but allowing help in the style of nchoosek), or not tell the user the dimensions of the output (another fine tradition).

Here then is my suggestion:

function x = nsumk(v,k)
% NSUMK Number or listing of non-negative integer n-tuples summing to k
% NSUMK(N,K) where N and K are positive integers returns nchoosek(K+N-1,N-1)
% This is the number of ordered N-tuples of non-negative integers summing to K
%
% NSUMK(V,K) where V is any vector of length n produces a matrix with
% nchoosek(K+N-1,N-1) rows and n columns. Each row comprises
% non-negative integers summing to k. The ordering of rows follows the
% same convention as NCHOOSEK, which is undocumented by Mathworks but with some
% reliability appears to be lexicographic. The reverse of this presumed ordering
% is a natural way to list coefficients of polynomials in N variables of degree K.
% As per nchoosek, this syntax is only practical for situations where N is
% less than about 15.

if isscalar(v),
x = nchoosek(k+v-1,v-1);
elseif isvector(v)
n = length(v);
nDividers = n-1;
nSpots = k+nDividers;
m = nchoosek(k+n-1,n-1);
dividers = [zeros(m,1),nchoosek((1:nSpots)',nDividers),ones(m,1)*(nSpots+1)];
x = diff(dividers,1,2)-1;
else
error('nsumk anticipates scalar or vector v');
end

You like ?

Kind Regards,

Peter

30 Jul 2010 John D'Errico

I am NOT proposing anything. I merely tried to read the help for your own function, then tried to convince you that your code needs documentation when used in a way that your help says is possible. Here are a couple of lines, written by you!

% Usage 2: x = nsumk(1:5,2)
%
% n: vector

Exactly how should your code work? What is the behavior of your code when it is passed a vector input for n? You need to define that. And to this point, I have seen no definition, no explanation. I've seen multiple references to nchoosek, that your code is related in some way to nchoosek. Therefore I assumed that when I call it in a way that I would call nchoosek, I might get a similar result. If this is false, then you need to document your own code properly. I am not suggesting any new functionality for this code. Merely that you document the EXISTING functionality so that a person who might want to use it can do so.

30 Jul 2010 Peter Cotton

Dearest John,

Thank you once again for your continued interest in this important matter.

And thank you for the idea of modifying the overloading of the first input argument. However clearly I might comment the help code for this new and improved function per you proposal, I fear that it may remain somewhat confusing. Your suggestion amounts to the following:

Usage 1: nsumk(n,k) returns the # of n-tuples summing to k
Usage 2: nsumk(v,k) where v is length (n+1) returns list of n-tuples summing to k

whereas at present:

Usage 1: nsumk(n,k) returns the # of n-tuples summing to k
Usage 2: nsumk(v,k) where v is length n, returns a list of n-tuples summing to k

I agree that the overloading is a little awkward either way but I don't think the former is an improvement over the latter.

I fear we may have strayed however in our joint undertaking to improve the help for this vital function. Perhaps we should consider more precisely which part of "n-tuples of non-negative integers adding up to k" you find unclear, and why it is that we should disqualify those deeply offensive numbers greater than n, as per your example of 4 and 5 above? I fear the vast community of users will be greatly disappointed should they struggle through my hopelessly unclear description only to find that nsumk(1:2,5) returns the empty set.

Kind regards,

Peter

30 Jul 2010 John D'Errico

Yes, but if you will argue that this code is in any way consistent with nchoosek, then it must be so. In the example I posed,

nsumk(1:3,5)

yields numbers that are not in that set! Zero is not in the set. 4 is not in the set. 5 is not in the set.

So clearly your code is not consistent with nchoosek, despite multiple statements that it is. You say what your code does and doe not require, but no place do you state that in the help. If you do not state what your code does, then how will anybody else ever find it of value?

Next, if you have lost the code before, then this is even a better reason to enable lookfor. Use an H1 line. Use a help style that at least tries to follow the style of help that the MathWorks uses. This makes your code more useful to others. Otherwise, it is of no use to anybody but you.

30 Jul 2010 Peter Cotton

John,

Thanks for the extremely speedy feedback.

Zero is a non-negative integer, and we do not require the integers here to be less than the number of variables. In generally accepted parlance the term tuple usually means an ordered list of elements, so I think the intent is clear. Sorry for my brevity. FYI it is a natural way to list polynomials in n variables of degree precisely k.

As is evident from the code this is little more than syntactic sugar for nchoosek, but since I've lost it once before I'm sticking it here!

Peter

30 Jul 2010 John D'Errico

Also, the help needs to be explicit about whether the pair of integers {2,3} is distinct from the pair {3,2}. I would argue that is an extremely important distinction. This code seems to count them both.

30 Jul 2010 John D'Errico

I would first point out that my own partitions.m solves exactly this problem, as well as a flexible variety of related problems.

http://www.mathworks.com/matlabcentral/fileexchange/12009

A quick test shows there to be a problem here though. Use nsumk to find all sums of tuples of the integers 1:3, that sums to 5. The help seems to indicate that this is possible, using the following call:

nsumk(1:3,5)
ans =
0 0 5
0 1 4
0 2 3
0 3 2
0 4 1
0 5 0
1 0 4
1 1 3
1 2 2
1 3 1
1 4 0
2 0 3
2 1 2
2 2 1
2 3 0
3 0 2
3 1 1
3 2 0
4 0 1
4 1 0
5 0 0

But clearly, that interpretation seems to fail, since nsumk uses 4 and 5 in those sums.

The help here seems reasonable, although it lacks an H1 line. AN H1 line is valuable when next month or next year, you simply cannot recall the name of that blasted function you wrote or downloaded long ago. It enables the function lookfor, which uses the very first line of your help. By putting a single line of intelligent description there, you can now use lookfor to do a keyword search of those H1 lines.

There are no error checks in this code. Of course, how can you check for errors when the help is not quite clear about what the arguments mean?

Updates
02 Aug 2010

I have included nsumkdaft.m which does the same thing using partitions.m

02 Aug 2010

Forgot to include partitions.m (required for nsumkdaft.m)

02 Aug 2010

Modified the extremely controversial overloading of the first argument

02 Aug 2010

Fixed upload error

03 Aug 2010

Modified documentation

06 Aug 2010

Modified comments

15 Aug 2010

Included link to vchoosek.m

Contact us