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

(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

(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

```