From: Pit Capitain <pit@...>
Date: 2003-04-21T18:26:09+09:00
Subject: Re: Biased weighted random?

On 21 Apr 2003 at 1:10, Mauricio Fern�ndez wrote about transition
matrices used for Hal's problem of "biases weighted random" 
sequences.

> (nice maths snipped)

How about the following approach, though mathematically not as 
interesting as transition matrices:

Given a set of values Vi and their desired number of occurrences in 
the final sequence Ni, it can be shown that there exists a sequence 
as Hal described if and only if

  max( Ni ) <= ( sum( Ni ) + 1 ) / 2

If anybody is interested in the proof, I can try to translate it to 
English and send it in another post.

Using this simple test you can implement the following algorithm 
based on the weighted random algorithm shown in other posts:


  def hal_sequence( values )
  
    sequence = []
    last_value = nil
    last_count = 0
    size = values.values.inject( 0 ) { | count, sum | sum + count }
    
    size.times do
      
      next_value = nil
      max = ( size + 1 ) / 2                               # (3)
      index = rand( size - last_count )                    # (1)
      
      values.each do
        | value, count |
        raise "no possible hal sequence" if count > max    # (3)
        if count == max && 2 * max > size                  # (4)
          next_value = value
          break
        end
        next if value == last_value                        # (1)
        next_value ||= value if ( index -= count ) < 0     # (5)
      end
      
      sequence << next_value
      last_value = next_value
      last_count = values[ last_value ] -= 1               # (2)
      values.delete( last_value ) if last_count <= 0       # (2)
      size -= 1
      
    end
  
    sequence
    
  end


Here are some examples:

  puts hal_sequence( 'a' => 3, 'b' => 4, 'c' => 3 ).join
  # => cbabcababc
  puts hal_sequence( 'a' => 3, 'b' => 6, 'c' => 3 ).join
  # => abcbabcbabcb
  puts hal_sequence( 'a' => 3, 'b' => 8, 'c' => 3 ).join
  # => ./hal.rb:17:in `hal_sequence': no possible hal sequence


Some notes about the algorithm:

(1) The last value taken and its count (remaining number of 
occurrences) is ignored when choosing the next random index and the 
next value.

(2) The remaining values Vi and their numbers of occurrences Ni are 
adjusted after each pass.

(3) The test for an existing "hal sequence" could be extracted out of 
the loop, but I like this code better.

(4) For each pass, if there's a value Vi with

  Ni == ( sum( Ni ) + 1 ) / 2

and sum( Ni ) is odd, then the next element in the sequence MUST be 
Vi (as well as every second remaining element).

(5) Because of (4), the loop cannot be exited after picking the next 
value based on the random index, for we have to test each value for 
the condition (4).


Regards,
Pit