[FIX] Re: [Squeak] Newbie permutations

Richard A. O'Keefe ok at cs.otago.ac.nz
Wed Apr 10 01:02:09 UTC 2002


Bijan Parsia <bparsia at email.unc.edu> wrote:
	Given that the selector is #permutationsDo:, it's perhaps worth having a
	separate method, #permutations, which would produce a collection of the
	distinct permuations. Then idioms like foo permutations select:...et al
	would work as expected.
	
Hands up all the people who _use_ #permutationsDo:?

Iterating over permutations is a standard technique in a class of
statistical techniques (appropriately called 'permutation-based methods'),
but statisticians know a thing or two about factorial.  So for any non-
trivial collection, they iterate over a random *sample* of permutations.
Why?  Because there are simply far too many permutations.

Let's put some explicit numbers on this.
I've forgotten the exact space model for Squeak, but let's suppose
an Array of n items costs n+2 words, and each word is 4 bytes.
How much space would we need for (1 to: n) permutations ?

(1 to: 12) collect: [:n |
    ( (n + 2) * n factorial " the permutations "
    + (n factorial + 2)	    " the array of permutations "
    ) * 4		    " words -> bytes "]

I get the answer 
#("0"          20
  "1"          24
  "2"          48
  "3"         152
  "4"         680
  "5"        3848
  "6"       25928
  "7"      201608
  "8"     1774088
  "9"    17418248
 "10"   188697608	"my machines could handle this"
 "11"  2235340808	"but not this"
 "12" 28740096008
)

Now, what use, is a 'return collection of all permutations' method
that is only usable for collections with at most 10 elements?

The code

    r := OrderedCollection new.
    s permutationsDo: [:each |
	(aBlock value: each) ifTrue: [r add: each copy]]

will work for more collections than the code

    s permutations select: aBlock

can _possibly_ work, as long as aBlock isn't true too often.

I haven't actually measured it, but from smaller probes I'd estimate
that my 250 MHz PowerMac would take about 3 hours to compute
(1 to: 10) asArray permutations, so I'm not _going_ to measure it.
(That's ignoring the fact that I only have 64MB of RAM...)

Just how much effort do we want put into methods of such limited utility?
Wouldn't the time be better spent writing a few class comments?

P.S.  There _is_ a bug in permtuationsDo:. 
(1 to: n) permutationsDo: doesn't work; this includes the example in
the method comment!

The simplest change I can think of is

permutationsDo: aBlock
    "Repeatedly value aBlock with a single copy of the receiver.
     Reorder the copy so that aBlock is presented all (self size factorial)
     possible permutations."
    "(1 to: 4) permutationsDo: [:each| Transcript cr; show: each printString]"
    |arr|
    arr := self asArray.
    arr == self ifTrue: [arr := arr copy].
    arr permutationsStartingAt: 1 do: aBlock




More information about the Squeak-dev mailing list