[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
	(then also
	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
are.  Try
    '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 mailing list