1
$\begingroup$

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

enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ "...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. $\endgroup$ – ciao Jul 3 '16 at 5:25
  • $\begingroup$ Thanks, I updated the question. Is it more clear now?. $\endgroup$ – jonaprieto Jul 3 '16 at 5:30
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If I want to cite your answer, how should I proceed? $\endgroup$ – jonaprieto Sep 17 '17 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$ – ciao Sep 17 '17 at 21:30
1
$\begingroup$

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

enter image description here

(* {{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]]

enter image description here

(* {{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}} *)
$\endgroup$
  • $\begingroup$ This will be excruciatingly slow for anything beyond trivial sizes, but interesting idea. $\endgroup$ – ciao Jul 3 '16 at 7:56
  • $\begingroup$ @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! $\endgroup$ – kirma Jul 3 '16 at 8:05
  • $\begingroup$ 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. $\endgroup$ – ciao Jul 3 '16 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.