[Squeak] Newbie permutations
Richard A. O'Keefe
ok at cs.otago.ac.nz
Tue Apr 9 23:57:14 UTC 2002
From: Markus Gaelli <gaelli at emergent.de>
I know at least about one other method, which is quite similar and
where you have to take care to copy each element.
SequencableCollection >> asDigitsToPower: anInteger do: aBlock
SequencableCollection >> asDigitsAt: 1 in: aCollection do: aBlock)
Read the comment: vvvvvv
"Repeatedly value aBlock with a single Array.
Adjust the collection so that aBlock is presented all
(self size raisedTo: anInteger) possible combinations
of the receiver's elements take as digits of an
anInteger long number."
The comment is a little misleading in that the elements of the
array need not be numbers, in fact it doesn't matter _what_ they
'abc' asDigitsToPower: 3 do: [:each | Transcript show: each; cr]
What it actually does it iterate over "all ordered samples of size anInteger
drawn with replacement from the receiver".
Note again that it's not a peculiarity of the implementation, but
a consequence of these facts:
- the number of iterations is exponential in the "size" of the input
(this is the most important point)
- the arguments presented to the block are arrangements of elements
of some collection
- the block is unlikely to need to keep a nontrivial proportion of the
arrangements; those it does need to keep it can easily copy for itself.
It is very easy to present small examples which can be iterated through
in a reasonable amount of time, but would turn over an unreasonable
amount of space if a new collection were allocated each time.
Myself, I'd be inclined to pass a single copy if the number of iterations
was more than linear in the "size" of the input.
More information about the Squeak-dev