[Squeak] Newbie permutations

Richard A. O'Keefe ok at cs.otago.ac.nz
Tue Apr 9 23:44:14 UTC 2002


Avi Bryant <avi at beta4.com> asked:
	#(1 3 5) permutationsDo: [:each | foo add: each copy]
	
	Is there a widespread convention at work here, or is this just a
	pecularity of the implementation of that particular method?
	
There are two particularly sensible conventions:
(0) Always pass the original object.
(1) Always pass a copy.

permutationsDo: does neither of these, and there are problem-specific
reasons for this.

- It doesn't pass the original object because if you exit part way through
  such an iteration, the original object will be left scrambled.  So at
  least one copy is required.

- It is easier to get 10**9 cycles of time than it is to get 10**9 bytes
  of space.  You can expect a modern machine to chomp through all
  (sequence size factorial) permutations in a reasonable time even when
  sequence size is as high as 12.  But you really DON'T want to thrash
  the memory management code by allocating all those copies, even if they
  aren't going to be kept.

- Many of the imaginable uses of permutationsDo: don't _need_ a fresh copy
  on each iteration, and those that do can easily make their own.
  (Thanks to the rate at which factorial grows, there aren't actually all
  that many _general_ uses of permutationsDo: in the first place.)
  So more than one copy is not required.

So the answer is "neither of the above".  It's not a widespread convention,
because there aren't that many iterations over rearrangements, and it's not
a peculiarity of the _implementation_, it's a peculiarity of the _task_.




More information about the Squeak-dev mailing list