On Jul 13, 2006, at 10:15 AM, Daniel Martin wrote:

> Ruby Quiz <james / grayproductions.net> writes:
>
>> Now that we know what to call them, the question becomes how do we
>> generate self documenting pangrams?  The linked article described a
>> technique called "Robbinsoning," which is a simple process.  The
>> idea is that you start with some random distribution of letter
>> counts, build the sentence, adjust the counts to reflect the actual
>> sentence counts, rebuild, adjust, etc.  You can zero in on a
>> solution in this fashion and most of the submitted solutions used
>> something along these lines.
>
> Note that the discussion of the different ways to solve this problem
> pointed up two distinctly different "randomized Robbinsoning"
> algorithms:
>
> 1) rebuild the sentence (or recalculate the frequencies) after each
> letter adjustment.  This was what my code did.
>
> 2) Go through each letter doing randomized adjustments then, after all
> letters have been adjusted, rebuild/recalculate.
>
> To have my program use this second algorithm, you can change the "if"
> bit in the main loop to:
>
>  	      actual2 = 0
>  	      lettershifts.each{ |y|
>  	        g = 0xFF & (guessfreq >> y)
>  	        a = 0xFF & (actualfreq >> y)
>  	        if (g != a)
>  	          d = (g-a).abs
>  	          r1 = rand(d+1)
>  	          r2 = rand(d+1)
>  	          r1=r2 if r1 < r2
>  	          r1=-r1 if a<g
>  	          if (r1 != 0) then
>  	            guessfreq += r1 << y
>                     g += r1
>  	          end
>  	        end
>                 actual2 += enfreq[g]
>  	      }
>  	      actualfreq = actual2
>
> But you *really* don't want to do that.  Adjusting all letters before
> recalculating the frequencies turns this consistently-under-30-seconds
> program into one that takes over an hour to complete.  Note that this
> second algorithm is the one followed by the perl script on the page
> linked to in the quiz description.
>
> Also note that Simon Kroeger's (first posted) solution follows this
> second algorithm but is still able to achieve phenomenally fast speed
> because he is able to push all the operations in the lettershifts loop
> above into NArray vector operations implemented in C.  In his
> alternate solution to this quiz, he uses the first algorithm but needs
> to loop over all the letter positions in ruby.  He reports that the
> increased speed of the first algorithm and the comparative slowness of
> doing the loop in ruby essentially cancel each other out, leading to
> both solutions being roughly equivalent in terms of speed.

Great info all around.

I didn't clue in to the two different algorithms.  Thanks for  
bringing that up!

James Edward Gray II