Random Matrix with criteria

Question

I want to construct $k$ lists $M$ of positions $(i,j)$ for a matrix $X$ of size $n\times m$, where all entries are "painted" with "white" color. The distribution of such a list $M$ must obey the following criteria:

• The length of list $M$ has to be exactly the size of a fixed percentage between $10%$ to $50%$ of $n\cdot m$. So, I choose this value.
• A valid position $(i,j)$ is when $1\leq i\leq n$, $1\leq j\leq m$, and
• If after we locate the positions of $M$ in the matrix $X$ painting them with "green", neither a column can be "green" nor a row. Indeed, both a row and a column must have at least two positions "white".
• The list $M$ has to be generated randomly.

I'd already done it, but the second restriction seems to so hard to fulfill. And, the code is so slow. My code is something around the use of RandomChoice. newij = RandomChoice[Outer[List, Range[n], Range[m]]; paint[newij]; do until we have all conditions.

This can be one of those random "paintings" for the matrix $X$:

Answer 1

Here's a quick-and-dirty method that does what (I think) you're after:

makearr[{n_, m_}, p_] := 
 Module[{base = PadLeft[ConstantArray[1, Round[n m p]], n m], cand},
  While[(cand = ArrayReshape[RandomSample@base, {n, m}]; 
    Max[Total[cand]] > n - 2 || Max[Total /@ cand] > m - 2)];
  Position[cand, 1]];

Example usage:

makearr[{5, 5}, .4]

{{1, 1}, {1, 3}, {2, 2}, {2, 5}, {3, 3}, {3, 5}, {4, 1}, {4, 2}, {5, 3}, {5, 5}}

Answer 2

If we ignore random sampling, this is a simple question of Boolean satisfiability:

Module[{m, n, greens, matrix, sol},
 m = 8;
 n = 5;
 greens = 20;
 matrix = Array[c, {m, n}];
 sol =
  matrix /. 
   First@FindInstance[
     And @@ (BooleanCountingFunction[Length@# - 2, Length@#] @@ # & /@
            matrix) &&
        And @@ (BooleanCountingFunction[Length@# - 2, 
              Length@#] @@ # & /@ Transpose@matrix) &&
        BooleanCountingFunction[{greens}, Length@#] @@ # &@
      Flatten@matrix, Flatten@matrix];
 sol // Boole // 
   MatrixPlot[#, Mesh -> All, 
     ColorFunction -> (If[# == 1, Green, White] &)] & // Echo;
 Position[sol, True]]

(* {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2},
    {3, 3}, {4, 1}, {4, 2}, {4, 3}, {5, 1}, {5, 2}, {5, 3}, {6, 1},
    {6, 2}, {6, 3}, {7, 4}, {7, 5}} *)

Well, that's not very random, and RandomSeed parameter doesn't help FindInstance in this case anyway.

A hack can be accomplished though, by sampling permuted candidates and choosing the first that fulfills the requirements:

Module[{m, n, greens, vals, matrix, check, sol},
 m = 8;
 n = 5;
 greens = 20;
 vals = Table[i <= greens, {i, m n}];
 matrix = Table[Quiet@#[[i, j]], {i, m}, {j, n}];
 check = Evaluate[
    And @@ (BooleanCountingFunction[Length@# - 2, Length@#] @@ # & /@ 
        matrix) &&
     And @@ (BooleanCountingFunction[Length@# - 2, Length@#] @@ # & /@
         Transpose@matrix)] &;
 sol = NestWhile[Partition[RandomSample@vals, n] &, 
   Partition[RandomSample@vals, n], check];
 sol // Boole // 
   MatrixPlot[#, Mesh -> All, 
     ColorFunction -> (If[# == 1, Green, White] &)] & // Echo;
 Position[sol, True]]

(* {{1, 1}, {1, 3}, {1, 5}, {2, 1}, {2, 2}, {2, 3}, {3, 2}, {3, 5},
    {4, 1}, {4, 2}, {4, 3}, {4, 4}, {5, 1}, {5, 2}, {5, 4}, {6, 2},
    {6, 5}, {7, 5}, {8, 2}, {8, 4}} *)