[Cuis-dev] [Integrated] Re: Fix for SequentiableCollection>>combinations:atATimeDo:

[Andres Valloud]

How about >20% faster in general?  I also fixed up comments that 
referenced methods and variables that didn't exist, etc.

I strongly suspect this iteration can be made to run faster still.

On 5/25/19 11:19, Luciano Notarfrancesco via Cuis-dev wrote:
> Hi Hernan,
> Thanks for integrating! Next time I should provide tests...
> Yes, it is expected behavior, it was made like that in order to 
> enumerate combinations as fast as possible without stressing the GC (I 
> wonder how much difference does it make nowadays, tho). I thought that 
> the name 'atATimeDo' was a remainder that the array is being reused in 
> each iteration, but actually groupsOf:atATimeDo: doesn't reuse the 
> array, and permutationsDo: reuses the array. IMHO groupsOf:do: and 
> combinationsOf:do: would be nicer names, but not a big deal.
> 
> 
> On Sat, May 25, 2019 at 1:06 PM Hernan Wilkinson 
> <hernan.wilkinson at 10pines.com <mailto:hernan.wilkinson at 10pines.com>> wrote:
> 
>     Hi Luciano,
>       thank you for the fix. It is integrated now and I added a couple
>     of tests to SequenceableCollectionTest, one when k is cero and
>     another for the normal case.
> 
>       When I wrote the test for the normal case I notice that the
>     collection passed as parameter to the block it is always the name
>     and therefore the following test fails:
>     testCombinationsAtATimeDoWorksAsExpected
> 
>     | combinations |
> 
>     combinations := OrderedCollection new.
>     'abc' combinations: 2 atATimeDo: [ :combination | combinations add:
>     combination].
> 
>     self assert: 3 equals: combinations size.
>     self assert: (combinations includes: #($a $b)).
>     self assert: (combinations includes: #($a $c)).
>     self assert: (combinations includes: #($b $c)).
> 
>     To make it pass I had to make a copy of combination.
>     ...
>     'abc' combinations: 2 atATimeDo: [ :combination | combinations add:
>     combination *copy*].
>     ....
> 
>     Is that the expected behavior? It looks weird to me... I would
>     expect combination to be different collections on each iteration...
> 
>     Cheers!
>     Hernan.
> 
>     On Thu, May 23, 2019 at 1:13 PM Luciano Notarfrancesco via Cuis-dev
>     <cuis-dev at lists.cuis.st <mailto:cuis-dev at lists.cuis.st>> wrote:
> 
>         The method was failing for the corner case of "combinations of 0
>         elements". Here's the fix.
>         -- 
>         Cuis-dev mailing list
>         Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>
>         https://lists.cuis.st/mailman/listinfo/cuis-dev
> 
> 
> 
>     -- 
>     *Hernán Wilkinson
>     Agile Software Development, Teaching & Coaching*
>     *Phone: +54-011*-4893-2057
>     *Twitter: @HernanWilkinson*
>     *site: http://www.10Pines.com <http://www.10pines.com/>*
>     Address: Alem 896, Floor 6, Buenos Aires, Argentina
> 
> 
-------------- next part --------------
'From Cuis 5.0 of 7 November 2016 [latest update: #3768] on 25 May 2019 at 1:24:40 pm'!

!SequenceableCollection methodsFor: 'private' stamp: 'sqr 5/25/2019 13:19:43'!
combinationsAt: j upTo: k in: aCollection after: m upTo: n do: aBlock
	"Choose k of N items and put in aCollection.  j-1 already chosen.  Indexes of items are in numerical order to avoid duplication.  In this slot, we are allowed to use items in self indexed by m+1 up to n.  m is the index used for position j-1."
	"(1 to: 6) combinations: 3 atATimeDo: [:each | Transcript cr; show: each printString]"

	m+1 to: n do: [:index | 
		aCollection at: j put: (self at: index).
		j = k
			ifTrue: [aBlock value: aCollection]
			ifFalse: [self combinationsAt: j + 1 upTo: k in: aCollection after: index upTo: n do: aBlock]]! !


!SequenceableCollection methodsFor: 'enumerating' stamp: 'sqr 5/25/2019 13:20:59'!
combinations: k atATimeDo: aBlock
	"Take the items in the receiver, k at a time, and evaluate the block for each combination.  Hand in an array of elements of self as the block argument.  Each combination only occurs once, and order of the elements does not matter.  There are (self size choose: k) combinations.

	 'abcde' combinations: 3 atATimeDo: [:each | Transcript newLine; show: each printString].
	"

	| aCollection |
	k = 0 ifTrue: [aBlock value: #(). ^ self].
	aCollection _ Array new: k.
	self combinationsAt: 1 upTo: k in: aCollection after: 0 upTo: self size do: aBlock! !

!methodRemoval: SequenceableCollection #combinationsAt:in:after:do:!
SequenceableCollection removeSelector: #combinationsAt:in:after:do:!
!methodRemoval: SequenceableCollection #combinationsAt:upTo:in:after:do:!
SequenceableCollection removeSelector: #combinationsAt:upTo:in:after:do:!