In article <[EMAIL PROTECTED]>,
Juho Snellman <[EMAIL PROTECTED]> writes:
> On Thu, Jan 29, 2004 at 04:26:41PM -0600, J. Riley Bryant wrote:
>> Assuming that we are randomly creating solutions 1e6
>> times, what is the probablilty that we will come up
>> with all permutations for up to 8 input letters
>> (assuming that the number of input letters is evenly
>> likely to be any value between 1 and 8)?
>
> I don't think that your analysis is valid, since sort { rand 2 }
> doesn't actually generate random solutions.
>
> % perl -le 'for (1..1e5) { $i = 0; $a[$i++][$_]++ for sort { rand 2 }
> 1..8}; print "@{$_}" for @a'
> 12557 12218 12578 12449 12412 12747 12445 12594
> 24750 25132 12493 12538 9418 9373 3133 3163
> 17271 17184 20183 20258 7048 6965 5566 5525
> 17972 18073 22636 22644 3509 3454 5968 5744
> 9323 9208 9654 9534 14651 14787 16318 16525
> 9035 9224 7244 7335 24458 24091 9370 9243
> 5129 5073 8608 8630 13684 13588 22744 22544
> 3963 3888 6604 6612 14820 14995 24456 24662
Even more relevant:
perl -wle '$c{"@{[sort { rand 2 } 1..8]}"}||=1 for 1..1e6; print scalar keys %c'
4096
You *cannot* make all orders using just 0 and 1.
(which is why in the fragment golf I used @a=sort{rand [EMAIL PROTECTED] (ok, there's
also the fact that sort does nothing in scalar context). You must
reshuffle to be able to reach all results. It's interesting to notice
that in that case the distribution becomes uniform too, the "initial state"
damps out exponentially).
>
> [ No, I don't understand why the distribution looks like that for
> the first element. ]
If you work it out, you'll see that the reachable space is always 2**m,
and that doesn't divide n! (m grows faster than n! picks up new powers
of 2), so the distribution cannot be uniform
>
> As for the other issue, I have no problem with letting the current
> results stand. But perhaps the "reasonable time" genrule might do with
> some tweaking for future golfs?
>
The limit is stated like that to allow clever very slow programs, and to
give you a good chance to survive "worst case", but the "limit computer"
is intentionally chosen slow so that in general you can actually test
within a day.
Having said that, I think mtve's should be rejected.
On a Real 366Mhz pentium II, I measure 7751 loops/second for a 8 piece input
(the sort speed depends critically on that), which gives
a runtime of 138753.507981 seconds. On a 100Mhz pentium II that is
5.9 days, and this was a 4-day golf => too slow.
To my mind, you won this golf (0olit3's is invalid too).
