[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
|