Rank: 5727 based on 0 downloads (last 30 days) and 1 file submitted
photo

Andy

E-mail

Personal Profile:
Professional Interests:

 

Watch this Author's files

 

Files Posted by Andy
Updated   File Tags Downloads
(last 30 days)
Comments Rating
03 Sep 2009 SUMM Function analogous to DIFF, but takes sums instead. Author: Andy sum, array 0 0
Comments and Ratings by Andy View all
Updated File Comments Rating
11 Jan 2011 setPrompt - Set the Command Window prompt Sets the Command Window prompt to the specified string Author: Yair Altman

I have a student edition of ML R2010a on Windows 7. It comes with the default prompt 'EDU>>', which I wanted to change back to the familiar '>>'. setPrompt worked, but it leaves too much space (copied and pasted):

EDU>> setPrompt('>>');
>> see how much space there is?

I would have preferred:

EDU>> setPrompt('>>');
>> only one space before text

Still, great stuff. Thanks, Yair!

04 Aug 2010 nsumk Returns the number and listing of n-tuples of non-negative integers adding up to k. Author: Peter Cotton

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 nsumk Returns the number and listing of n-tuples of non-negative integers adding up to k. Author: Peter Cotton

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 nsumk Returns the number and listing of n-tuples of non-negative integers adding up to k. Author: Peter Cotton

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 nsumk Returns the number and listing of n-tuples of non-negative integers adding up to k. Author: Peter Cotton

"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.

Top Tags Applied by Andy
array, sum
Files Tagged by Andy
Updated   File Tags Downloads
(last 30 days)
Comments Rating
03 Sep 2009 SUMM Function analogous to DIFF, but takes sums instead. Author: Andy sum, array 0 0

Contact us at files@mathworks.com