Hi Richard,

I had a feeling you'd pipe up.  Your code is very pretty.  I couldn't
help but run some timings against the code already in the image.  The
numbers in quotes are the parameters ("n:k range), and the numbers
below them are the millisecond timings.  Of course, these don't mean
too much without some actual work in the block.


[(1 to: n) asArray choose: k do: [:ignore | ]] timeToRun
"20:5-10"
 28
 74
 151
 257
 363
 420

"25:10-12"
 6473
 9248
 11170

"26:12-13"
 16588
 18856


[(1 to: n) asArray combinations: k atATimeDo: [:ignore | ]] timeToRun
"20:5-10"
 20
 53
 126
 250
 416
 597

"25:10-12"
 6539
 10828
 16265

"26:12-13"
 27382
 34975


Thanks,
Joshua


On Fri, May 23, 2003 at 05:13:47PM +1200, Richard A. O'Keefe wrote:
> "Joshua 'Schwa' Gargus" <schwa at cc.gatech.edu> asked:
> 	Does anyone have code that does something like:
> 	
> 	aCollection choose: 3 do: [:array | ...]
> 	
> 	where each possible unordered collection of 3 elements (ie:
> 	"n-choose-k", where n is the size of aCollection and k is here 3) is
> 	chosen from aCollection and passed as the argument to the block?
> 	
> Well, I do, for Prolog.  But it's pretty rather than useful,
> because n-choose-k gets big FAST.
> 
> Let's see how we might do this.
> 
> To choose k items out of n:
>    If n < k, we can't do it.
>    If k = 0 we are done.
>    If k > 0, then
>       Either we take item n and choose k-1 from n-1,
>       or we choose k from n-1.
> 
> So here we go.  I'm going to put this in Array.
> 
> Array methods for 'enumerating'
> 
>     choose: k of: n into: workingArray do: aBlock
>         n < k ifTrue: [^self].
>         k = 0 ifTrue: [^aBlock value: workingArray].
>         workingArray at: k put: (self at: n).
>         self choose: k-1 of: n-1 into: workingArray do: aBlock.
>         self choose: k of: n-1 into: workingArray do: aBlock.
> 
>     choose: k do: aBlock
> 	|workingArray|
> 	workingArray := Array new: k.
> 	self choose: k of: self size into: workingArray do: aBlock.
> 
> If you want this for other collections, stick
> 
>     choose: k do: aBlock
> 	self asArray choose: k do: aBlock
> 
> in Collection.
> 
> For example, #(a b c d) choose: 2 do: ... reports
> #(c d), #(b d), #(a d), #(b c), #(a c), #(a b)
> in that order.
>