[Tutor] Filling an array - with a twist

[Richard Damon]

On 11/11/20 1:30 AM, Phil wrote:
> Another call on the Brains Trust I'm afraid.
>
> I'd like to fill an 8 x 8 array (list of lists) with random numbers
> such that no column or row repeats the same number more than twice in
> a sequence.
>
> e.g.. [12344562] is OK but [12223456] is not wanted.
>
> Something like the following will give me a row or column that meets
> the requirements but more often than not fails the complete array test.
>
> >>> import random
> >>> r = random.sample(range(0,8),8)
> >>> r
> [6, 2, 4, 5, 3, 0, 1, 7]
>
> Searching through the array trying to repair an errant sequence is not
> the answer. Can anyone suggest an algorithm to do what I need?
>
> To add to the complication I really need numbers between 0 and 6 which
> random.sample() won't allow because, as the value error states, the
> sample is larger than the population.
>
This doesn't sound like a 'common' problem so likely nothing build in
will fully deal with it. My thought on the simple (but maybe not
shortest) way to fill in like that is iterate through you locations,
fill in with a random value, and then check if it is the third of that
value in the row or column, and if so, repeat again.

For your modification with 7 values and an 8x8 grid, there is one
possible issue with the last point that there may be only one
possibility, if the column has 3 repeated values and the row and 3
different repeated values.

If you find the fail and need to draw again gets repeated values and
loops on trying the same number too much (I don't think it will), you
could change to make a random draw from a list, which you start with all
the values, and when you find a bad value (by trying it) you remove it
from the list of possibilities, so you can't get that one for this
location again. That will say that the above degenerate case is
guaranteed to find the open value in no more than 7 trials, instead of
an expected value of 7 trials, but might go with 'bad luck' much longer.
It will slow down the normal case by creating the list each time, so
probably hurts the average case to help the worse case.

-- 
Richard Damon