# Random Matrix with criteria

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$:

• "...a list M..." and "... the positions of M..." don't make sense together - do you mean the positions listed in M? Please, post your code (slow or not) and some kind of examples showing initial and desired results. As it is, I for one can't decipher this.
– ciao
Jul 3 '16 at 5:25
• Thanks, I updated the question. Is it more clear now?. Jul 3 '16 at 5:30

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

• If I want to cite your answer, how should I proceed? Sep 17 '17 at 19:24
• You have permission to use this, or any of my answers on mathematica.stackexchange without attribution. If you want to link to it as part of a citation, use whatever citation format floats your boat.
– ciao
Sep 17 '17 at 21:30

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}} *)

• This will be excruciatingly slow for anything beyond trivial sizes, but interesting idea.
– ciao
Jul 3 '16 at 7:56
• @ciao Well, it's slow for anything where probability of random permutation being a valid solution is low, but not necessarily for all big matrices. My approach is more a demonstration of "FindInstance would be great if it had reliable random sampling built in it", but since that isn't the case, a bit flawed in practice! Jul 3 '16 at 8:05
• I don't think the "probability of random permutation being a valid solution is low..." is the issue, try e.g. a 100x100 matrix with .01% (1) "greens" - the probability of a permutation not being valid is zero.
– ciao
Jul 3 '16 at 8:14