There's a distinction between the algorithm and the implementation: Using for. instead of rank is an implementation detail--it can slow you down, but the asymptotic time remains the same. It's quite possible that the performance of comb could be improved by using tacit code.
The difference here is the algorithm: this method lists every subset of the list and filters by length. Therefore it operates in O(2^n) time and space, because it lists all 2^n subsets. An efficient algorithm can use recursion to only list the correct combinations, giving it time O(x ! y). Marshall On Tue, Sep 27, 2011 at 9:00 PM, David Vaughan <[email protected] > wrote: > Thanks. > > I thought that using for. constructs incurred a time penalty, but the > version without it is slower: > > comb2 is also equivalent to comb , but requires space (and time) > exponential in the size of the result. > > > comb2=: ((= +/"1) |.@:I.@# ]) #:@i.@(2&^) > Why is this? > > On 28 Sep 2011, at 01:53, Henry Rich wrote: > > > http://www.jsoftware.com/jwiki/Essays/Combinations > > > > Henry Rich > > > > On 9/27/2011 8:50 PM, David Vaughan wrote: > >> How could I list all combinations of x!y? > >> > >> e.g. 2!3 = 3, and the combinations are (1,2), (1,3), (2,3). > >> > >> Thanks. > >> ---------------------------------------------------------------------- > >> For information about J forums see http://www.jsoftware.com/forums.htm > >> > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
