How to populate a $0-$line with $1$'s?

Question

I have a line of $n$ $0$'s like this:

Zeroth index -->$000...000$

I want to populate the line with $m$ $1$'s with the following rules:

(1) They have to occur after the index $i_{\text{start}_n}$ and before the index $i_{\text{end}_n}$.

(2) There must be at least three $0$'s between any two $1$'s.

(3) The positions are random within the above two constraints.

(4) $i_{\text{start}_n}<i_{\text{end}_n}<n-1$

(5) $\color{red}{m<?}$

How can this insertion be performed, and what are the constraints on $\color{red}{m}$?

Answer 1

Attach a zero to each side of each $1$, then insert the $m$ "$010$" units into a line of $(n-2m)$ zeroes (including potentially before and after).

This is possible in ${n-2m+1 \choose m}$ ways.

Clearly we need $(n-2m+1) \ge m \implies m \le \frac{n+1}{3}$

---

Algorithmically, finding positions for the $m$ $1$s can use the above insertion process as follows:

• Find $n'= i_{end}-i_{start}+1$
• Randomly choose $m$ distinct numbers in the range $0$ to $(n'-2m)$
• With the numbers in ascending order $\{a_1, a_2, \ldots, a_m\}$, modify them by adding $2(k-1)+i_{start}$ to each $a_k$.
• These values are insertion points in the string of $0$s - they do not refer to position in the final string. Each $1$ goes after the $0$ at the indicated position.

Answer 2

<?php
function UniqueRandomNumbersWithinRange($min, $max, $quantity) {
            $numbers = range($min, $max);
            shuffle($numbers);
            return array_slice($numbers, 0, $quantity);
}

for( $i=0 ; $i < 20 ; $i++ ){//20 instances

    $numbers = UniqueRandomNumbersWithinRange(0, 204-1-3-9+1-2*10, 10);//204 events

    sort($numbers);

    echo var_dump($numbers)."<br/>";//show numbers before adding 2(k-1)+i_start

    foreach( $numbers as $key=>$num ){
         $numbers[$key] = $num+2*($key+1-1)+9;
    }

    echo "FINAL ARRAY: ";
    echo var_dump($numbers)."<br/><br/>";//show numbers after adding 2(k-1)+i_start
}

?>